Timeline for Is $AC^0/poly \cap NP$ contained in $P$?
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 13, 2016 at 13:23 | comment | added | Yuval Filmus | @Vincent It's encoded in binary (more accurately, take the $|x|$'th string in non-decreasing order of length). | |
| Jul 13, 2016 at 13:20 | comment | added | Vincent | yes that is what confuses me. If $|x|$ is the length of some string, then $|x|$ is an integer, so how can it be an element of $\Lambda$? | |
| Jul 13, 2016 at 13:14 | comment | added | Yuval Filmus | @Vincent Here $x$ is a string rather than an integer, and $|x|$ is its length. | |
| Jul 13, 2016 at 11:49 | comment | added | Vincent | Just to be sure: do I understand correctly that $|x|$ is the length of $x$ written in unary? | |
| Jan 30, 2013 at 1:37 | comment | added | Tsuyoshi Ito | Essentially the same transformation is used in Book 1974 to show that E≠NE if and only if NP∖P contains a tally language. | |
| Oct 7, 2010 at 8:40 | comment | added | Dai Le | Nice answer Yuval! | |
| Oct 7, 2010 at 4:22 | vote | accept | Kaveh | ||
| Oct 6, 2010 at 21:47 | history | answered | Yuval Filmus | CC BY-SA 2.5 |