# The cozy neighborhoods of “P” and of “NP-hard”

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 Yuval Filmus' 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 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.

-
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 Dec 22 '12 at 17:16
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 Dec 22 '12 at 19:05
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 Dec 22 '12 at 21:09
(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 Dec 22 '12 at 21:31
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 Dec 22 '12 at 23:12

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.

-
Dear Scott, many thanks for the answer! – Gil Kalai Dec 25 '12 at 6:21
@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 Dec 26 '12 at 7:25
Here are their papers: cs.berkeley.edu/~luca/pubs/redux-sicomp.pdf people.csail.mit.edu/akavia/2006-stocAGGM.pdf (see also erratum at 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 Dec 26 '12 at 22:27
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 Dec 26 '12 at 22:39
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 Dec 27 '12 at 1:00

Russell Impagliazzo's proof of Ladner's theorem 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 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.

-
I might be missing something, but wouldn't ANY proof of Ladner's Theorem work just as well here? – Scott Aaronson Dec 24 '12 at 12:55
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 Dec 24 '12 at 15:33
Dear Yuval, many thanks for the answer! – Gil Kalai Dec 24 '12 at 18:07
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 Dec 24 '12 at 19:43

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.

-
Dear Andy, many thanks for the answer! – Gil Kalai Dec 25 '12 at 6:20

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.

-
Dear Andy, many thanks for this additional answer! – Gil Kalai Dec 26 '12 at 19:33

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. 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)

-
The result about average-case hardness of the permanent was improved by Cai, Pavan and Sivakumar in pages.cs.wisc.edu/~jyc/papers/permanent.pdf – arnab Dec 27 '12 at 0:01