tag:blogger.com,1999:blog-3722233.post90013764..comments2024-07-08T08:20:09.315-05:00Comments on Computational Complexity: Foundations of ComplexityLesson 9: NondeterminismLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-40936184520522588802024-03-11T09:48:22.095-05:002024-03-11T09:48:22.095-05:00Yes, that definition works.Yes, that definition works.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62271093454635679032024-03-10T16:38:11.259-05:002024-03-10T16:38:11.259-05:00OK. I missed the “and only if”. Would the followin...OK. I missed the “and only if”. Would the following be equivalent?<br />L is in NP if there is a polynomial p and a deterministic Turing machine M such that for all x in L, there is a w, |w| ≤ p(|x|) and M(x,w) accepts in time at most p(|x|), and for all x not in L, for all w, M(x,w) rejects. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80916295477239013952024-03-07T07:41:56.683-06:002024-03-07T07:41:56.683-06:00It doesn't matter--you can just add a clock an...It doesn't matter--you can just add a clock and halt M(x,w) after p(|x|) steps and reject.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81956696394103354152024-03-06T19:32:16.956-06:002024-03-06T19:32:16.956-06:00The definition of NP misses an important piece. M ...The definition of NP misses an important piece. M must reject any x that is not in the language for all w.Anonymousnoreply@blogger.com