Timeline for The NP version of Matiyasevich's theorem
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 20, 2011 at 16:20 | vote | accept | CommunityBot | moved from User.Id=6976 by developer User.Id=69903 | |
| Jul 20, 2011 at 14:51 | comment | added | Kaveh | I see. (I didn't pay attention that 𝖣𝖫𝖮𝖦𝖳𝖨𝖬𝖤 uniformity is not good for 𝖭𝖢𝟢.) | |
| Jul 20, 2011 at 14:17 | comment | added | Emil Jeřábek | How do you define uniform $\mathrm{NC}^0$, anyway? As mentioned in Pollett’s paper, all NP-sets are bounded Diophantine if all coNLOGTIME-sets are, so the closure under any class of at least this complexity (which is quite small) is equivalent to the full problem. | |
| Jul 20, 2011 at 14:03 | comment | added | Kaveh | Emil, is it known if they are closed under any smaller complexity class like $\mathsf{NC^0}$? | |
| Jul 20, 2011 at 13:46 | history | answered | Emil Jeřábek | CC BY-SA 3.0 |