Timeline for Bounds on reducing from NP to SAT
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 7, 2011 at 10:57 | comment | added | Tsuyoshi Ito | My previous comment is wrong, because the time complexity of the reduction can be any polynomial depending on the language. | |
| Oct 7, 2011 at 4:11 | comment | added | Kaveh | note: there is a meta-discussion about the recent questions in complexity including this one here. | |
| Oct 7, 2011 at 2:43 | comment | added | Tsuyoshi Ito | It is impossible because it would contradict the nondeterministic time hierarchy theorem. en.wikipedia.org/wiki/… | |
| Oct 7, 2011 at 0:44 | history | asked | circuits | CC BY-SA 3.0 |