That's right! I completely flubbed that part while doing some other edits! Thanks. What I wanted to say is there are O1 and O2 such that: P^O1 strict subset NP^O1 and P^O2 equals NP^O2
I think RJ Lipton (blog author) and Knuth believe it could be true. However, most complexity theorists don't (I think Fortnow does a survey of theorists on this every few years). Knuth says something like "well all it…
Maybe this will help with understand the revitalization barrier. Most proof of separations of complexity classes relativize, in that not only do they show A strict subset B they also show A^O strict subset B^O for ANY…
Great post. Here are a few things pointers if you want more information about your points: B) The situation is actually worse than exhausted. We know (have proven) that the regular methods simply won't work (check up…
Sorry, somehow I missed that in the abstract.
No, the distribution is thought to be hard for any classical algorithm (this is still being worked on - there are still ongoing theory development for showing it is harder and harder), and by extension, any classical…
It is a bit more difficult to see this because you are describing a continuous time process, however, the answer is that yes you would be able to to figure out the time t1 given you knew had a snapshot of the whole…
That's right! I completely flubbed that part while doing some other edits! Thanks. What I wanted to say is there are O1 and O2 such that: P^O1 strict subset NP^O1 and P^O2 equals NP^O2
I think RJ Lipton (blog author) and Knuth believe it could be true. However, most complexity theorists don't (I think Fortnow does a survey of theorists on this every few years). Knuth says something like "well all it…
Maybe this will help with understand the revitalization barrier. Most proof of separations of complexity classes relativize, in that not only do they show A strict subset B they also show A^O strict subset B^O for ANY…
Great post. Here are a few things pointers if you want more information about your points: B) The situation is actually worse than exhausted. We know (have proven) that the regular methods simply won't work (check up…
Sorry, somehow I missed that in the abstract.
No, the distribution is thought to be hard for any classical algorithm (this is still being worked on - there are still ongoing theory development for showing it is harder and harder), and by extension, any classical…
It is a bit more difficult to see this because you are describing a continuous time process, however, the answer is that yes you would be able to to figure out the time t1 given you knew had a snapshot of the whole…