- Does the polynomial-time hierarchy look like the arithmetic hierarchy? I mentioned this in the centenary post for Mostowski. Probably not because it would imply factoring in P (since NP∩co-NP would equal P) but we have no proof of separation and no oracle that makes them look the same.
- Does UP = NP imply the polynomial-time hierarchy collapses? What are the consequences if SAT had an NP algorithm with a unique accepting path? Remains open, again even in relativized worlds.
- Do rational functions that agree with Boolean functions on the hypercube have low decision tree complexity? I really expected someone to have come up with a proof or counterexample by now.
- What happens if two queries to NP can be simulated by a single query? Does S2=ZPPNP? Both questions asked in a post on S2P.
- Separate NP from Logarithmic space. I gave four approaches in a pre-blog 2001 survey on diagonalization (Section 3) though none have panned out. Should be much easier than separating P from NP.
Thursday, May 05, 2016
Through the years I've mentioned a few of my favorite open problems in computational complexity on this blog that have perplexed me through the years. Let me mention a few of them again in case they inspire some of the new generation of complexity theorists.