Timeline for answer to Relation of Space and Time in Complexity? by David Richerby
Current License: CC BY-SA 3.0
Post Revisions
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28, 2014 at 0:04 | vote | accept | EthanLWillis | ||
| Feb 27, 2014 at 21:56 | comment | added | David Richerby | Yes and no. Remember that every problem in P is also in NP, as you can think of a deterministic TM as a trivial case of a nondeterministic TM (it just only ever makes nondeterministic choices from a single option). Finding an efficient way to be smart about which branch to simulate would certainly be one way of proving P = NP but it's possible that there are other ways, too. | |
| Feb 27, 2014 at 21:35 | comment | added | EthanLWillis | Thank you for your reply. So basically what P=NP boils down to is: Is there any way to create a problem in P that is equivalent to a problem in NP by choosing "smartly" which branches of an NTM to simulate on a DTM? | |
| Feb 27, 2014 at 21:03 | history | answered | David Richerby | CC BY-SA 3.0 |