<p><a href="http://blog.computationalcomplexity.org/media/ladner.pdf">Russell Impagliazzo's proof of Ladner's theorem</a> furnishes an example for 3. For completeness' sake, below I copy the definition of the algorithmic task $X$ and sketch the proof that it is on "both sides", in a strong sense: in both cases, PH collapses to P. More details can be found in the linked note (taken from Fortnow and Gasarch's blog), which is (lightly) adapted from the appendix to <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.64.5432&amp;rep=rep1&amp;type=pdf">Uniformly Hard Sets</a> by Downey and Fortnow.</p>

<p>Let $M_i$ be an enumeration of all clocked polytime Turing machines, such that $M_i$ terminates in time $n^{\log\log i}$. In the sequel, we will mention pairs $(\alpha,\beta)$. These are assumed to be encoded as binary strings in some reasonable manner.</p>

<p>We define recursively a function $f(n)$. First, $f(1) = 1$. Given $f(n)$, $f(n+1)$ is defined as follows. Let $X_n$ consist of all pairs $(\phi,1^{|\phi|^{f(|\phi|)}})$ such that $|\phi| \leq n$ and $\phi$ is a satisfiable formula.
If there is a binary string $x$ of length at most $\log n$ such that $x \in L(M_{f(n)}) \triangle X_n$ then $f(n+1) = f(n)+1$, otherwise $f(n+1) = f(n)$. It is not hard to check that $f(n)$ can be calculated in time polynomial in $n$.</p>

<p>Finally, we can define the algorithmic task $X$: it consists of all pairs $(\phi,1^{|\phi|^{f(|\phi|)}})$ for which $\phi$ is a satisfiable CNF. Note that $X = \bigcup_n X_n$.</p>

<p>If $X$ had a polytime algorithm $M_i$ then $f(n) \leq i$ for all $n$ and so $M_i$ can be used to solve SAT.</p>

<p>Next, suppose there were a polytime reduction $g$ from SAT to $X$, say taking time $n^k$. If $X$ had a polytime algorithm then as we have seen PH collapses to P. Otherwise, $f(n) \longrightarrow \infty$, and in particular, $f(n) &gt; k$ for $n \geq n_0$. The reduction $g$ thus takes any instance of SAT of size larger than $n_0$ and either reduces it to a smaller instance, or outputs a string which is not of the form $(\phi,1^{|\phi|^{f(|\phi|)}})$; the latter case can be recognized in polytime since $f$ is polytime. Iterating $g$, we obtain a polytime algorithm for SAT.</p>

CC BY-SA 3.0
2012-12-24T12:55:23.087Z
I might be missing something, but wouldn't ANY proof of Ladner's Theorem work just as well here?
Scott Aaronson
CC BY-SA 3.0
2012-12-24T15:33:18.043Z
Probably, but I think Gil is looking for "natural" examples with "convincing" proofs. As I have commented above, it is better not to take 3 in a strict logical sense, since then it is equivalent to the collapsing of PH.
Yuval Filmus
CC BY-SA 3.0
2012-12-24T19:43:41.283Z
Dear Yuval, Scott, all,  I wonder (this is part 2 of my question) if problems on the NP-side (including the one above) are "morally NP hard" in the sense that they manifest the hardness of SAT. Of course, this is a question about our current ability to prove such results and not a strict cc question. I am mainly interested (part 1) in more examples (the more natural the merrier) in the P-side and NP-side. (As Yuval explained, Lander's theorem settles part 3) of my question. It is nice to see the details of Russell's proof explained.)
Gil Kalai
CC BY-SA 3.0
2012-12-23T22:23:17.577Z
2012-12-23T22:23:17.577Z
Yuval Filmus
<p>Two comments, neither of which amount to an answer, but which may provide some useful further reading.</p>

<p>1)  Schöning defined two classes of NP problems called the "Low Hierarchy" and the "High Hierarchy", that are related to your notions.  In particular, problems in LowH are "on the P-side", and problems in HighH are on the NP-side.  A number of well-known results in complexity can be stated in this framework.  For example, the Karp-Lipton theorem says that NP is not in P/poly unless PH collapses; this is a consequence of the fact that NP $\cap$ P/poly is contained in a fixed level of LowH (as the Karp-Lipton proof technique shows).  Note that we don't expect that NP $\cap$ P/poly, or LowH, is contained in P.
For a survey on LowH in particular, see</p>

<p><a href="http://www.informatik.hu-berlin.de/forschung/gebiete/algorithmenII/Publikationen/Abstracts/low.ps.abstr_html">http://www.informatik.hu-berlin.de/forschung/gebiete/algorithmenII/Publikationen/Abstracts/low.ps.abstr_html</a></p>

<p>2)  Consider the problem where we are given a full truth table of a Boolean function, and asked if it has a Boolean circuit of some size $t$.  This problem is in NP, and unlikely to be in P (it would imply several surprising consequences).  On the other hand, a proof of NP-completeness for this problem, if it obeys certain fairly natural restrictions, would give us powerful new results in complexity theory.  This was shown by Kabanets and Cai in</p>

<p><a href="http://eccc.hpi-web.de/report/1999/045/">http://eccc.hpi-web.de/report/1999/045/</a></p>

<p>To be clear, there's no real evidence that this problem is <em>not</em> NP-hard, or that it is easy in any sense.  But it seems quite different from other hard problems in NP.  I think this is among the most interesting candidates for NP-intermediate problems, and not one that is well-known.</p>

CC BY-SA 3.0
2012-12-24T21:22:05.350Z
2012-12-24T21:22:05.350Z
Andy Drucker
<p>The very terms "on the P-side" and "on the NP-side," and of course the question title, encourage us to imagine a "cozy neighborhood" surrounding P and another "cozy neighborhood" surrounding the NP-hard problems.  However, I'd like to argue that these two neighborhoods are not so "cozy" at all!</p>

<p>As a first observation, there are problems "on the P-side" that seem "morally" much closer to NP-hard than to P.  One example, anticipated by Gil of course, is the general problem of inverting one-way functions (depending on exactly what type of reductions are allowed; see Bogdanov-Trevisan or Akavia et al.).</p>

<p>Conversely, there are also problems "on the NP-side" that seem "arbitrarily far" from being NP-hard.  One silly example is a random language L, with probability 1 over L!  For if such an L is in P, then 0=1 and math is inconsistent, and therefore PH collapses also. ;-D</p>

<p>(Note that a random language L is <i>also</i> "on the P-side," with probability 1 over L.  For almost all such L's have the property that if they're NP-hard, then NP&sube;BPP and PH collapses.  And this gives a proof, much simpler than the appeal to Ladner's Theorem, that there exist languages on both "sides."  Indeed, it shows that of the uncountable infinity of languages, "almost all" of them -- in fact, 100% -- are on both sides!)</p>

<p>This sounds like juvenile game-playing, but there's a serious lesson I'd like to draw from it.  I'd argue that, even though QUANTUM SAMPLING is formally "on the NP-side," that problem is barely any closer to being "morally NP-hard" than the random language L was.  Arkhipov and I (and independently, Bremner-Jozsa-Shepherd) showed that, if QUANTUM SAMPLING is in P (or rather, in SampBPP, the class of polynomially-solvable sampling problems), then P<sup>#P</sup> = BPP<sup>NP</sup>, and therefore the polynomial hierarchy collapses.  Yet if you're a BPP machine, an oracle for BosonSampling would, as far as we know, bring you no closer to solving NP-complete problems than a random oracle would.  Only if you <i>already</i> have the ability to solve NP-complete problems -- say, if you're a BPP<sup>NP</sup> machine -- do you "notice" that the BosonSampling oracle boosts your capabilities even further, to #P.  But the property of boosting NP up to #P seems different than, and maybe even "orthogonal to," the property of being NP-hard on one's own.</p>

<p>Incidentally, a wonderful open problem suggested by Gil's question is whether BosonSampling is also "on the P-side."  That is, can we show that if NP reduces to BosonSampling then PH collapses?  While I might be missing something obvious, at first glance I have no clue how to prove such a thing, any more than I know how to prove the stronger implication that if NP &sube; BQP then PH collapses.</p>

CC BY-SA 3.0
2012-12-26T06:16:34.757Z
Regarding the last paragraph it is also interesting if QUANTUM SAMPLING or BOSONSAMPLING (even just in an approximate sense) can be achieved in a comouter with SAMPBPP capabilities which, in addition, is given the ability to solve BQP problems.
Gil Kalai
CC BY-SA 3.0
2012-12-26T07:25:42.817Z
@Gil: I agree, that's an excellent question.  As Alex and I point out in Section 4.1 of our paper, if that were so, then P^#P would be contained in BPP^NP^BQP.  Which seems unlikely to me, though I admit to lacking a strong intuition!
Scott Aaronson
CC BY-SA 3.0
2012-12-26T19:38:52.907Z
BTW Scott, the paragraph about one-way functions, Bogdanov-Trevisan and Akavia is not clear to me. re: QUANTUM SAMPLING it is a mystery for me if it is genuinly harder than BQP or the difference is just an artifact of the cc lenses we use.
Gil Kalai
CC BY-SA 3.0
2012-12-26T22:27:49.307Z
Here are their papers: http://www.cs.berkeley.edu/~luca/pubs/redux-sicomp.pdf  http://people.csail.mit.edu/akavia/2006-stocAGGM.pdf (see also erratum at http://people.csail.mit.edu/akavia/AGGM_errata.pdf)  (There was also earlier related work by Feigenbaum and Fortnow.)  Basically they show that if inverting a one-way function is NP-hard under *randomized, nonadaptive reductions*, then PH collapses.  The case of adaptive reductions remains open.
Scott Aaronson
CC BY-SA 3.0
2012-12-26T22:39:47.230Z
Regarding QSAMPLING, I could easily believe that BPP^NP^QSAMPLING is strictly larger than BPP^NP^BQP (even though, of course, I don't know for sure).  But as I see it, this would tell us less about "inherent differences" between QSAMPLING and BQP, than simply about differences in the oracle access mechanism!  Recall especially that, by our definitions, the BPP^NP machine gets to CHOOSE the random bits used by the quantum sampling oracle.  And even a practical quantum computer wouldn't provide that randomness-fixing capability, although a classical simulation of a QC *would* provide it.
Scott Aaronson
CC BY-SA 3.0
2012-12-26T22:52:50.860Z
This is interesting! The cc point of view gives a  classification which is based on  reductions (and not on the anticipated running times). So I regard factoring in the P-side although it may well be exponential, and therefore in some other sense "much closer" to NP complete problems. Similarly, having inverting one way function in the P-side seems reasonable, and I am not sure in what sense those are morally "much closer" to being NP-hard.
Gil Kalai
CC BY-SA 3.0
2012-12-27T01:00:46.277Z
Gil: Well, inverting one-way functions is provably *equivalent* to solving NP-complete problems, except with two changes: (1) you don't need to handle worst-case instances but only average-case (w.r.t. efficiently-samplable distributions), and (2) the same sampling procedure that generates the instances also generates satisfying assignments for them.
Scott Aaronson
CC BY-SA 3.0
2012-12-27T08:45:32.993Z
Scott, For "genuine" examples, I think that the P-side indeed contains also problems which are "morally NP-hard" where the NP-hardness is weakened in a provable way. The NP-side seems more robust so the cozy neighborhood description may be more appropriate. QSAMPLING is a big mystery. Is it in a cozy neoghborhood of NP hard? Is it genuinly harder than BQP? or it is just the different algorithmic caracters? For examlpe, I dont know how to compare BPPSAMPLING and BPP and what the answer is. You may ask, e.g., if a polylog depth probabilistic computer with access to BPP subroutine can BPPsample.
Gil Kalai
CC BY-SA 3.0
2012-12-25T01:00:37.250Z
2012-12-25T14:34:21.497Z
2012-12-25T14:34:21.497Z
Scott Aaronson
<p>The hypothesis that the Polynomial Hierarchy does not collapse has been one of the most fertile paths to discovery in complexity theory.  Many of these results can be phrased as saying that specific algorithmic tasks are "on the P-side" or "on the NP-side".  $PH$ non-collapse seems to have many more consequences than the weaker hypothesis $P \neq NP$, and it would be impossible to corral them all into a single brief post.  Let me just give three examples that give a small sense of the variety of this work.</p>

<p>1)  Suppose we are given as input a circuit with "oracle gates," that makes two oracle queries during any computation.  We want to know whether it accepts when run on a $SAT$ oracle.  Of course, this is $NP$-hard.  But suppose we would be content to reduce the circuit to an equivalent one that makes just a single query to $SAT$.  Is even this task hard?  We don't know if solving it would imply $P = NP$.  However, Kadin in '88 showed that doing so would collapse the Poly Hierarchy.  For a survey and improved result, see this paper of Fortnow, Pavan, and Sengupta:</p>

<p><a href="http://people.cs.uchicago.edu/~fortnow/papers/2q.pdf">http://people.cs.uchicago.edu/~fortnow/papers/2q.pdf</a></p>

<p>2)  Suppose we are given a $SAT$ instance $\psi$ of size $m$, with only $n \ll m$ Boolean variables.  Can we efficiently "shrink" $\psi$ to a satisfiability-equivalent formula of size bounded by some fixed polynomial in $n$ (independent of $m$)?  This would be a valuable preprocessing step before running an exponential-time algorithm.  Such a reduction would also be a strong expression of the idea that the hardness of $SAT$ derives primarily from the dimension of an instance's solution-search space.</p>

<p>In answer to a question of Bodlaender, Downey, Fellows, and Hermelin, it was shown by Fortnow and Santhanam that such a compression reduction is unlikely, because it would collapse the Poly Hierarchy:</p>

<p><a href="http://people.cs.uchicago.edu/~fortnow/papers/compress.pdf">http://people.cs.uchicago.edu/~fortnow/papers/compress.pdf</a></p>

<p>Their result applied to randomized reductions allowing one-sided error.  I proved a corresponding result for two-sided error in</p>

<p><a href="http://eccc.hpi-web.de/report/2012/112/">http://eccc.hpi-web.de/report/2012/112/</a></p>

<p>(Each of these papers actually gives stronger and more specific information than the results quoted above.)</p>

<p>3) Sometimes we want to prove a problem is hard using the $PH$ non-collapse assumption, but no such result seems forthcoming.  It's sometimes possible to use oracles to explain why.  For example, we'd love to be able to show that the class $PPAD$, which expresses the hardness of finding fixed points of continuous functions (and Nash equilibria of games) is hard assuming $PH$ is infinite.  But Buhrman et al. showed that there is an oracle $A$ which $PPAD^A$ (and all other problems in the class $TFNP^A$) are easy, yet $PH^A$ is infinite: </p>

<p><a href="http://people.cs.uchicago.edu/~fortnow/papers/phq.pdf">http://people.cs.uchicago.edu/~fortnow/papers/phq.pdf</a></p>

<p>Some people dispute the importance of oracle results, but I think there is no question that they can save complexity theorists from pursuing fruitless lines of inquiry.  This is definitely one such case.  (Basically all known proofs of form "$X$ in $P$ $\Rightarrow$ $PH$ collapses" are relativizing, AFAIK.)  It points to the limitations of the $PH$ non-collapse assumption and the importance of exploring additional hypotheses.</p>

CC BY-SA 3.0
2012-12-26T19:33:03.020Z
Dear Andy, many thanks for this additional answer!
Gil Kalai
CC BY-SA 3.0
2012-12-26T18:38:00.510Z
2012-12-26T19:20:40.040Z
2012-12-26T19:20:40.040Z
Andy Drucker
<p>I came accross this result by Feige and Lund which shows that unless the polynomial hierarchy collapses it is hard to guess even very partial information about the permanent of a random matrix.</p>

<p>Uriel Feige and Carsten Lund, <a href="http://www.wisdom.weizmann.ac.il/~feige/Others/permanent.ps" rel="nofollow">On the Hardness of Computing the Permanent of Random Matrices.</a>
Computational Complexity 6 (1996/1997) 101-132.</p>

<p>Let me also mention two additional relevant results brought to my attention from Uri Feige:</p>

<p>The following two papers apply this in the context of kernelization (fixed parameter tractable algorithms).</p>

<p>Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8): 423-434 (2009)</p>

<p>Lance Fortnow, Rahul Santhanam: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1): 91-106 (2011)</p>

CC BY-SA 3.0
2012-12-27T00:01:12.693Z
The result about average-case hardness of the permanent was improved by Cai, Pavan and Sivakumar in http://pages.cs.wisc.edu/~jyc/papers/permanent.pdf
arnab
CC BY-SA 3.0
2012-12-26T05:49:33.900Z
2013-01-03T13:23:45.063Z
2013-01-03T13:23:45.063Z
Gil Kalai
<p>Let $X$ be an algorithmic task. (It can be a decision problem or an optimization problem or any other task.) Let us call $X$ "on the polynomial side" if assuming that $X$ is NP-hard is known to imply that the polynomial hieararchy collapses. Let us call $X$ "on the NP-side" if assuming that $X$ admits a polynomial algorithm is known to imply that the polynomial hierarchy collapses. </p>

<p>Of course, every problem in P is on the polynomial side and every problem which is NP-hard is in the NP-side. Also, for example, factoring (or anything in NP intersection coNP) is on the polynomial side. Graph isomorphism is on the polynomial side. QUANTUM-SAMPLING is in the NP-side.</p>

<p>1) I am interested in more examples (as natural as possible) of algoritmic tasks in the polynomial side and (especially) in more examples in the NP side.</p>

<p>2) Naively it looks that the NP side is a sort of a "neighborhood" of the NP-hard problems, and the P-side is a "neighborhood of P".  Is it a correct insight to regard problems in the NP side as "considerably harder" compared to problems in the P side. Or even to regard problems in the NP side as "morally NP-hard?" </p>

<p>3) (This might be obvious but I don't see it) Is there an $X$ on both sides or are there theoretical reasons to believe that such an $X$ is unlikely. <strong>Update</strong> The answer is YES; see Yuval Filmus' answer below.</p>

<p>(If these "sides" are related to actual complexity classes and if I miss some relevant cc jargon or relevant results please let me know.)  </p>

<p><strong>Update:</strong> There are by now several very good answers to the question. As noted first by Yuval Filmus and mentioned again the question is not formal and some restriction on the argument showing that X is on the P-side/NP-side is needed. (Otherwise, you can have X to be the task of presenting a proof for 0=1 which is on both sides.) Putting this aside, it may be the case that problems X (genuinly) on the NP-side capture somehow the hardness of SAT, although this may also be the case for some problems on the P-side where the hardness of SAT is weakened (even slightly) in a provable way. Yuval Filmus gave a weakened version of SAT which is on both sides. Andy Drucker gave (in two answers) five interesting examples including a reference to Schöning's Low and High hierarchies, and Scott Aaronson gave further interesting examples, mentioned the question of inverting a one-way function which is close to capture NP hardness and yet on the P-side,  and his answer also discusses the interesting case of QUANTUMSAMPLING. I metioned an old result of this kind by Feige and Lund.</p>

CC BY-SA 3.0
2012-12-22T17:14:11.457Z
There is a problem with a statement of the form "if X is NP-hard then PH collapses", if you believe that X is either NP-hard or not NP-hard (it could also be independent). Perhaps you mean a stronger statement like "in any relativized world, if X is NP-hard then PH collapses", though that's also problematic, since if X is in P then X is in P in any relativized world.
Yuval Filmus
CC BY-SA 3.0
2012-12-22T17:16:11.657Z
Re 3, if you believe that PH does not collapse, then there is some NP-intermediate problem X. Since X is neither NP-hard nor in P, then X is "on both sides", yet PH does not collapse, so 3 is false. On the other hand, if PH does collapse, then 3 is true. So 3 $\leftrightarrow$ PH collapses.
Yuval Filmus
CC BY-SA 3.0
2012-12-22T18:30:53.193Z
@YuvalFilmus Possibly Gil means "there is a proof that if X is NP-hard then PH collapses". Thus if it is possible to prove PH doesn't collapse then X is NP side iff X can be proved to lie outside of P. Similarly for P side. If it is possible to prove PH collapses then everything is on both sides. However if PH collapse is independent then P/NP side is a non-trivial property
Vanessa
CC BY-SA 3.0
2012-12-22T19:05:55.507Z
A proof in what proof system? Also, in any particular model of "the world" (whatever proof system one usually works in), then either PH collapses or it doesn't, unless we work in intuitionist logic.
Yuval Filmus
CC BY-SA 3.0
2012-12-22T19:31:57.883Z
@YuvalFilmus Well for any given axiom system we get some notion of "P side" and "NP side". PH either collapses or not but if the statement is independent in the given axiom system then the corresponding "side" notions are potentially non-trivial
Vanessa
CC BY-SA 3.0
2012-12-22T21:09:07.873Z
Dear Yuval and Squark, Hmmm, maybe instead of taliking about "cause" or "prove" it is better to simply say that X is in the P side if it is known that if X is NP-hard then PH collapses, and X is in the NP side if it is known that if X is in P then the PH collapses. (Questions 1 and 2 remains unchanged and question 3 asks if there is an X on both sides or some theoretical reason that no such X is possible.)
Gil Kalai
CC BY-SA 3.0
2012-12-22T21:31:19.390Z
(Anyway, in order to avoid the difficulties you raise which are interesting but not essential to the question I will reformulate the question.)
Gil Kalai
CC BY-SA 3.0
2012-12-22T23:12:59.283Z
GK suspect there might be some question here that has nothing to do with PH collapsing but maybe is just about different complexity classes between P and NP complete... frankly it sounds like a question about how the (proven-to-exist) Hartmanis-Sterns time hierarchy maps onto P vs NP... that thm proves there is a continuum, and complexity classes prove (if they exist) there are very significant "discontinuities" in this continuum... also Ladners thm seems relevant...
vzn
CC BY-SA 3.0
2012-12-23T05:56:00.657Z
Yuval, Re 3 the question is this: Is there an algorithmic tast X for which it is known both that if X is in P, PH cpllapses and that if X is  NP-hard, PH collapses? or perhaps this is unlikely because  by itself it demonstrates some CC statement which is  out of reach. (The most extreme case will be that proving such a statement about X implies some seperation of complexity classes, but there can be weaker consequences which are already unrealistic.)
Gil Kalai
<cc.complexity-theory>
The cozy neighborhoods of "P" and of "NP-hard"
Gil Kalai
# The cozy neighborhoods of "P" and of "NP-hard"

(Asked by: username_0 on 2012-12-22)

Let $X$ be an algorithmic task. (It can be a decision problem or an optimization problem or any other task.) Let us call $X$ "on the polynomial side" if assuming that $X$ is NP-hard is known to imply that the polynomial hieararchy collapses. Let us call $X$ "on the NP-side" if assuming that $X$ admits a polynomial algorithm is known to imply that the polynomial hierarchy collapses.

Of course, every problem in P is on the polynomial side and every problem which is NP-hard is in the NP-side. Also, for example, factoring (or anything in NP intersection coNP) is on the polynomial side. Graph isomorphism is on the polynomial side. QUANTUM-SAMPLING is in the NP-side.

1) I am interested in more examples (as natural as possible) of algoritmic tasks in the polynomial side and (especially) in more examples in the NP side.

2) Naively it looks that the NP side is a sort of a "neighborhood" of the NP-hard problems, and the P-side is a "neighborhood of P". Is it a correct insight to regard problems in the NP side as "considerably harder" compared to problems in the P side. Or even to regard problems in the NP side as "morally NP-hard?"

3) (This might be obvious but I don't see it) Is there an $X$ on both sides or are there theoretical reasons to believe that such an $X$ is unlikely. **Update** The answer is YES; see username_1' answer below.

(If these "sides" are related to actual complexity classes and if I miss some relevant cc jargon or relevant results please let me know.)

**Update:** There are by now several very good answers to the question. As noted first by username_1 and mentioned again the question is not formal and some restriction on the argument showing that X is on the P-side/NP-side is needed. (Otherwise, you can have X to be the task of presenting a proof for 0=1 which is on both sides.) Putting this aside, it may be the case that problems X (genuinly) on the NP-side capture somehow the hardness of SAT, although this may also be the case for some problems on the P-side where the hardness of SAT is weakened (even slightly) in a provable way. username_1 gave a weakened version of SAT which is on both sides. username_5 gave (in two answers) five interesting examples including a reference to Schöning's Low and High hierarchies, and username_4 gave further interesting examples, mentioned the question of inverting a one-way function which is close to capture NP hardness and yet on the P-side, and his answer also discusses the interesting case of QUANTUMSAMPLING. I metioned an old result of this kind by Feige and Lund.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: There is a problem with a statement of the form "if X is NP-hard then PH collapses", if you believe that X is either NP-hard or not NP-hard (it could also be independent). Perhaps you mean a stronger statement like "in any relativized world, if X is NP-hard then PH collapses", though that's also problematic, since if X is in P then X is in P in any relativized world.  
> **username_1**: Re 3, if you believe that PH does not collapse, then there is some NP-intermediate problem X. Since X is neither NP-hard nor in P, then X is "on both sides", yet PH does not collapse, so 3 is false. On the other hand, if PH does collapse, then 3 is true. So 3 $\leftrightarrow$ PH collapses.  
> **username_2**: @YuvalFilmus Possibly Gil means "there is a proof that if X is NP-hard then PH collapses". Thus if it is possible to prove PH doesn't collapse then X is NP side iff X can be proved to lie outside of P. Similarly for P side. If it is possible to prove PH collapses then everything is on both sides. However if PH collapse is independent then P/NP side is a non-trivial property  
> **username_1**: A proof in what proof system? Also, in any particular model of "the world" (whatever proof system one usually works in), then either PH collapses or it doesn't, unless we work in intuitionist logic.  
> **username_2**: @YuvalFilmus Well for any given axiom system we get some notion of "P side" and "NP side". PH either collapses or not but if the statement is independent in the given axiom system then the corresponding "side" notions are potentially non-trivial  
> **username_0**: Dear Yuval and Squark, Hmmm, maybe instead of taliking about "cause" or "prove" it is better to simply say that X is in the P side if it is known that if X is NP-hard then PH collapses, and X is in the NP side if it is known that if X is in P then the PH collapses. (Questions 1 and 2 remains unchanged and question 3 asks if there is an X on both sides or some theoretical reason that no such X is possible.)  
> **username_0**: (Anyway, in order to avoid the difficulties you raise which are interesting but not essential to the question I will reformulate the question.)  
> **username_3**: GK suspect there might be some question here that has nothing to do with PH collapsing but maybe is just about different complexity classes between P and NP complete... frankly it sounds like a question about how the (proven-to-exist) Hartmanis-Sterns time hierarchy maps onto P vs NP... that thm proves there is a continuum, and complexity classes prove (if they exist) there are very significant "discontinuities" in this continuum... also Ladners thm seems relevant...  
> **username_0**: Yuval, Re 3 the question is this: Is there an algorithmic tast X for which it is known both that if X is in P, PH cpllapses and that if X is  NP-hard, PH collapses? or perhaps this is unlikely because  by itself it demonstrates some CC statement which is  out of reach. (The most extreme case will be that proving such a statement about X implies some seperation of complexity classes, but there can be weaker consequences which are already unrealistic.)  

---

## 5 answers

### Answer by username_4 on 2012-12-25. Score: 28

The very terms "on the P-side" and "on the NP-side," and of course the question title, encourage us to imagine a "cozy neighborhood" surrounding P and another "cozy neighborhood" surrounding the NP-hard problems. However, I'd like to argue that these two neighborhoods are not so "cozy" at all!

As a first observation, there are problems "on the P-side" that seem "morally" much closer to NP-hard than to P. One example, anticipated by Gil of course, is the general problem of inverting one-way functions (depending on exactly what type of reductions are allowed; see Bogdanov-Trevisan or Akavia et al.).

Conversely, there are also problems "on the NP-side" that seem "arbitrarily far" from being NP-hard. One silly example is a random language L, with probability 1 over L! For if such an L is in P, then 0=1 and math is inconsistent, and therefore PH collapses also. ;-D

(Note that a random language L is *also* "on the P-side," with probability 1 over L. For almost all such L's have the property that if they're NP-hard, then NP⊆BPP and PH collapses. And this gives a proof, much simpler than the appeal to Ladner's Theorem, that there exist languages on both "sides." Indeed, it shows that of the uncountable infinity of languages, "almost all" of them -- in fact, 100% -- are on both sides!)

This sounds like juvenile game-playing, but there's a serious lesson I'd like to draw from it. I'd argue that, even though QUANTUM SAMPLING is formally "on the NP-side," that problem is barely any closer to being "morally NP-hard" than the random language L was. Arkhipov and I (and independently, Bremner-Jozsa-Shepherd) showed that, if QUANTUM SAMPLING is in P (or rather, in SampBPP, the class of polynomially-solvable sampling problems), then P#P = BPPNP, and therefore the polynomial hierarchy collapses. Yet if you're a BPP machine, an oracle for BosonSampling would, as far as we know, bring you no closer to solving NP-complete problems than a random oracle would. Only if you *already* have the ability to solve NP-complete problems -- say, if you're a BPPNP machine -- do you "notice" that the BosonSampling oracle boosts your capabilities even further, to #P. But the property of boosting NP up to #P seems different than, and maybe even "orthogonal to," the property of being NP-hard on one's own.

Incidentally, a wonderful open problem suggested by Gil's question is whether BosonSampling is also "on the P-side." That is, can we show that if NP reduces to BosonSampling then PH collapses? While I might be missing something obvious, at first glance I have no clue how to prove such a thing, any more than I know how to prove the stronger implication that if NP ⊆ BQP then PH collapses.

> **Comments:**
> **username_0**: Regarding the last paragraph it is also interesting if QUANTUM SAMPLING or BOSONSAMPLING (even just in an approximate sense) can be achieved in a comouter with SAMPBPP capabilities which, in addition, is given the ability to solve BQP problems.  
> **username_4**: @Gil: I agree, that's an excellent question.  As Alex and I point out in Section 4.1 of our paper, if that were so, then P^#P would be contained in BPP^NP^BQP.  Which seems unlikely to me, though I admit to lacking a strong intuition!  
> **username_0**: BTW Scott, the paragraph about one-way functions, Bogdanov-Trevisan and Akavia is not clear to me. re: QUANTUM SAMPLING it is a mystery for me if it is genuinly harder than BQP or the difference is just an artifact of the cc lenses we use.  
> **username_4**: Here are their papers: http://www.cs.berkeley.edu/~luca/pubs/redux-sicomp.pdf  http://people.csail.mit.edu/akavia/2006-stocAGGM.pdf (see also erratum at http://people.csail.mit.edu/akavia/AGGM_errata.pdf)  (There was also earlier related work by Feigenbaum and Fortnow.)  Basically they show that if inverting a one-way function is NP-hard under *randomized, nonadaptive reductions*, then PH collapses.  The case of adaptive reductions remains open.  
> **username_4**: Regarding QSAMPLING, I could easily believe that BPP^NP^QSAMPLING is strictly larger than BPP^NP^BQP (even though, of course, I don't know for sure).  But as I see it, this would tell us less about "inherent differences" between QSAMPLING and BQP, than simply about differences in the oracle access mechanism!  Recall especially that, by our definitions, the BPP^NP machine gets to CHOOSE the random bits used by the quantum sampling oracle.  And even a practical quantum computer wouldn't provide that randomness-fixing capability, although a classical simulation of a QC *would* provide it.  
> **username_0**: This is interesting! The cc point of view gives a  classification which is based on  reductions (and not on the anticipated running times). So I regard factoring in the P-side although it may well be exponential, and therefore in some other sense "much closer" to NP complete problems. Similarly, having inverting one way function in the P-side seems reasonable, and I am not sure in what sense those are morally "much closer" to being NP-hard.  
> **username_4**: Gil: Well, inverting one-way functions is provably *equivalent* to solving NP-complete problems, except with two changes: (1) you don't need to handle worst-case instances but only average-case (w.r.t. efficiently-samplable distributions), and (2) the same sampling procedure that generates the instances also generates satisfying assignments for them.  
> **username_0**: Scott, For "genuine" examples, I think that the P-side indeed contains also problems which are "morally NP-hard" where the NP-hardness is weakened in a provable way. The NP-side seems more robust so the cozy neighborhood description may be more appropriate. QSAMPLING is a big mystery. Is it in a cozy neoghborhood of NP hard? Is it genuinly harder than BQP? or it is just the different algorithmic caracters? For examlpe, I dont know how to compare BPPSAMPLING and BPP and what the answer is. You may ask, e.g., if a polylog depth probabilistic computer with access to BPP subroutine can BPPsample.  

---

### Answer by username_1 on 2012-12-23. Score: 20

[Russell Impagliazzo's proof of Ladner's theorem](http://blog.computationalcomplexity.org/media/ladner.pdf) furnishes an example for 3. For completeness' sake, below I copy the definition of the algorithmic task $X$ and sketch the proof that it is on "both sides", in a strong sense: in both cases, PH collapses to P. More details can be found in the linked note (taken from Fortnow and Gasarch's blog), which is (lightly) adapted from the appendix to [Uniformly Hard Sets](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.64.5432&rep=rep1&type=pdf) by Downey and Fortnow.

Let $M\_i$ be an enumeration of all clocked polytime Turing machines, such that $M\_i$ terminates in time $n^{\log\log i}$. In the sequel, we will mention pairs $(\alpha,\beta)$. These are assumed to be encoded as binary strings in some reasonable manner.

We define recursively a function $f(n)$. First, $f(1) = 1$. Given $f(n)$, $f(n+1)$ is defined as follows. Let $X\_n$ consist of all pairs $(\phi,1^{|\phi|^{f(|\phi|)}})$ such that $|\phi| \leq n$ and $\phi$ is a satisfiable formula.
If there is a binary string $x$ of length at most $\log n$ such that $x \in L(M\_{f(n)}) \triangle X\_n$ then $f(n+1) = f(n)+1$, otherwise $f(n+1) = f(n)$. It is not hard to check that $f(n)$ can be calculated in time polynomial in $n$.

Finally, we can define the algorithmic task $X$: it consists of all pairs $(\phi,1^{|\phi|^{f(|\phi|)}})$ for which $\phi$ is a satisfiable CNF. Note that $X = \bigcup\_n X\_n$.

If $X$ had a polytime algorithm $M\_i$ then $f(n) \leq i$ for all $n$ and so $M\_i$ can be used to solve SAT.

Next, suppose there were a polytime reduction $g$ from SAT to $X$, say taking time $n^k$. If $X$ had a polytime algorithm then as we have seen PH collapses to P. Otherwise, $f(n) \longrightarrow \infty$, and in particular, $f(n) > k$ for $n \geq n\_0$. The reduction $g$ thus takes any instance of SAT of size larger than $n\_0$ and either reduces it to a smaller instance, or outputs a string which is not of the form $(\phi,1^{|\phi|^{f(|\phi|)}})$; the latter case can be recognized in polytime since $f$ is polytime. Iterating $g$, we obtain a polytime algorithm for SAT.

> **Comments:**
> **username_4**: I might be missing something, but wouldn't ANY proof of Ladner's Theorem work just as well here?  
> **username_1**: Probably, but I think Gil is looking for "natural" examples with "convincing" proofs. As I have commented above, it is better not to take 3 in a strict logical sense, since then it is equivalent to the collapsing of PH.  
> **username_0**: Dear Yuval, Scott, all,  I wonder (this is part 2 of my question) if problems on the NP-side (including the one above) are "morally NP hard" in the sense that they manifest the hardness of SAT. Of course, this is a question about our current ability to prove such results and not a strict cc question. I am mainly interested (part 1) in more examples (the more natural the merrier) in the P-side and NP-side. (As Yuval explained, Lander's theorem settles part 3) of my question. It is nice to see the details of Russell's proof explained.)  

---

### Answer by username_5 on 2012-12-24. Score: 20

Two comments, neither of which amount to an answer, but which may provide some useful further reading.

1) Schöning defined two classes of NP problems called the "Low Hierarchy" and the "High Hierarchy", that are related to your notions. In particular, problems in LowH are "on the P-side", and problems in HighH are on the NP-side. A number of well-known results in complexity can be stated in this framework. For example, the Karp-Lipton theorem says that NP is not in P/poly unless PH collapses; this is a consequence of the fact that NP $\cap$ P/poly is contained in a fixed level of LowH (as the Karp-Lipton proof technique shows). Note that we don't expect that NP $\cap$ P/poly, or LowH, is contained in P.
For a survey on LowH in particular, see

<http://www.informatik.hu-berlin.de/forschung/gebiete/algorithmenII/Publikationen/Abstracts/low.ps.abstr_html>

2) Consider the problem where we are given a full truth table of a Boolean function, and asked if it has a Boolean circuit of some size $t$. This problem is in NP, and unlikely to be in P (it would imply several surprising consequences). On the other hand, a proof of NP-completeness for this problem, if it obeys certain fairly natural restrictions, would give us powerful new results in complexity theory. This was shown by Kabanets and Cai in

<http://eccc.hpi-web.de/report/1999/045/>

To be clear, there's no real evidence that this problem is *not* NP-hard, or that it is easy in any sense. But it seems quite different from other hard problems in NP. I think this is among the most interesting candidates for NP-intermediate problems, and not one that is well-known.


---

### Answer by username_5 on 2012-12-26. Score: 11

The hypothesis that the Polynomial Hierarchy does not collapse has been one of the most fertile paths to discovery in complexity theory. Many of these results can be phrased as saying that specific algorithmic tasks are "on the P-side" or "on the NP-side". $PH$ non-collapse seems to have many more consequences than the weaker hypothesis $P \neq NP$, and it would be impossible to corral them all into a single brief post. Let me just give three examples that give a small sense of the variety of this work.

1) Suppose we are given as input a circuit with "oracle gates," that makes two oracle queries during any computation. We want to know whether it accepts when run on a $SAT$ oracle. Of course, this is $NP$-hard. But suppose we would be content to reduce the circuit to an equivalent one that makes just a single query to $SAT$. Is even this task hard? We don't know if solving it would imply $P = NP$. However, Kadin in '88 showed that doing so would collapse the Poly Hierarchy. For a survey and improved result, see this paper of Fortnow, Pavan, and Sengupta:

<http://people.cs.uchicago.edu/~fortnow/papers/2q.pdf>

2) Suppose we are given a $SAT$ instance $\psi$ of size $m$, with only $n \ll m$ Boolean variables. Can we efficiently "shrink" $\psi$ to a satisfiability-equivalent formula of size bounded by some fixed polynomial in $n$ (independent of $m$)? This would be a valuable preprocessing step before running an exponential-time algorithm. Such a reduction would also be a strong expression of the idea that the hardness of $SAT$ derives primarily from the dimension of an instance's solution-search space.

In answer to a question of Bodlaender, Downey, Fellows, and Hermelin, it was shown by Fortnow and Santhanam that such a compression reduction is unlikely, because it would collapse the Poly Hierarchy:

<http://people.cs.uchicago.edu/~fortnow/papers/compress.pdf>

Their result applied to randomized reductions allowing one-sided error. I proved a corresponding result for two-sided error in

<http://eccc.hpi-web.de/report/2012/112/>

(Each of these papers actually gives stronger and more specific information than the results quoted above.)

3) Sometimes we want to prove a problem is hard using the $PH$ non-collapse assumption, but no such result seems forthcoming. It's sometimes possible to use oracles to explain why. For example, we'd love to be able to show that the class $PPAD$, which expresses the hardness of finding fixed points of continuous functions (and Nash equilibria of games) is hard assuming $PH$ is infinite. But Buhrman et al. showed that there is an oracle $A$ which $PPAD^A$ (and all other problems in the class $TFNP^A$) are easy, yet $PH^A$ is infinite:

<http://people.cs.uchicago.edu/~fortnow/papers/phq.pdf>

Some people dispute the importance of oracle results, but I think there is no question that they can save complexity theorists from pursuing fruitless lines of inquiry. This is definitely one such case. (Basically all known proofs of form "$X$ in $P$ $\Rightarrow$ $PH$ collapses" are relativizing, AFAIK.) It points to the limitations of the $PH$ non-collapse assumption and the importance of exploring additional hypotheses.

> **Comments:**
> **username_0**: Dear Andy, many thanks for this additional answer!  

---

### Answer by username_0 on 2012-12-26. Score: 10

I came accross this result by Feige and Lund which shows that unless the polynomial hierarchy collapses it is hard to guess even very partial information about the permanent of a random matrix.

Uriel Feige and Carsten Lund, [On the Hardness of Computing the Permanent of Random Matrices.](http://www.wisdom.weizmann.ac.il/~feige/Others/permanent.ps)
Computational Complexity 6 (1996/1997) 101-132.

Let me also mention two additional relevant results brought to my attention from Uri Feige:

The following two papers apply this in the context of kernelization (fixed parameter tractable algorithms).

Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8): 423-434 (2009)

Lance Fortnow, Rahul Santhanam: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1): 91-106 (2011)

> **Comments:**
> **username_6**: The result about average-case hardness of the permanent was improved by Cai, Pavan and Sivakumar in http://pages.cs.wisc.edu/~jyc/papers/permanent.pdf  

---

