Timeline for Are there any undecidability results that are not known to have a diagonal argument proof?
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 10 at 18:13 | comment | added | Timothy Chow | @StevenStadnicki There are non-relativizing separations, such as Vinodchandran's result that $\mathsf{PP}$ does not have size $n^k$ circuits, but I'm not sure they help answer the original question either. | |
| Mar 10 at 17:57 | comment | added | Steven Stadnicki | Unfortunately, the main non-relativizing complexity result I know is a positive one (IP = PSPACE) so it's not really an example for OP. | |
| Sep 8, 2023 at 8:56 | history | edited | Timothy Chow | CC BY-SA 4.0 |
Edited for clarity
|
| Sep 7, 2023 at 2:33 | history | answered | Timothy Chow | CC BY-SA 4.0 |