That’s a nice downward collapse.

But, I could not understand the proof. I guess I am missing something in the above proof.

How does the P machine (that tries to simulate the YP computation) run the E machine in polynomial time?

Moreover, where is the assumption E=NE^NP^NP used? It seems the specified computation on (n,k) can be carried out by an E machine (without any assumptions).

Did you mean if E=NE^NP^NP then

we get some collapse involving YE?

Suppose E = NE^NP^NP; then we can simulate a YP machine as follows. Given an input of size n, for each k from 1 up to poly(n), feed <n,k> to an E machine. The E machine answers the following question:

Does there exist a witness w of size poly(n), such that

(1) For all inputs x of size n, the YP machine produces an answer given x and w.

(2) For all w’ that lexicographically precede w, there exists an x of size n such that the YP machine produces no answer given x and w’.

(3) The k^th bit of w is a 1.

From the answers to these questions, we can read off the

lexicographically first valid YP witness, then use that witness to

decide any input of size n we want.

Thanks to Andy D. and Venkat for catching my oversight.

]]>We got more interested in ONP after relaizing that ONP forms an hierachy similar to PH. Namely, P, ONP, coONP, ONP^ONP, co-ONP^ONP etc. This whole hiearchy is contained in O_2^p (the oblivious analog of S_2^p). Thus, O_2^p is like PSPACE and the above ONP hierarchy is like PH. And we found it curious to see such a situation existing inside P/poly.

One question: I don’t see why

YP=P ==> NE=E.

I was able to only show that

ONP=P ==> NE=E.

I am sure I am missing something (and also I did not read all the comments to this post carefully).

As I said before, one can show that if P=YP then E=NE and EXP=NEXP.

Regarding your “big-picture” question, right now we have more fertile hardness assumptions than we know what to do with! Here are just a few of them:

* E!=NE (even EE!=NEE and EEE!=NEEE have been used…).

* NP is hard on average.

* One-way functions exist.

* The Unique Games conjecture.

* BPP!=BQP.

* E requires exponential-size circuits.

* FPT!=W[1] (the fixed-parameter tractability hypothesis).

* Permanent does not have poly-size arithmetic circuits.

I’m sure people can suggest others that I forgot…

]]>*I suspect that if YP = P, there is some unlikely collapse somewhere else.*

Maybe, but bear in mind: YP is in NP intsect coNP;

in ECCC TR06-024, Buhrman, Fortnow, et al. showed an oracle where the PH is infinite yet P = NP intsect coNP (among other features).

Which occasions a big-picture question I’ve wanted to ask complexity theorists:

The hypothesis ‘P != NP’ historically seems to have been eclipsed by the more fertile hypothesis ‘PH is infinite’ as a guide to research. But is the latter now exhausting its fertility as a source of interesting, provable implications? If so, what are attractive candidates for the next big hypotheses?

]]>