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

Question

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.

Answer 1

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 = BPP^NP, 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 BPP^NP 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.

Answer 2

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 3

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.

Answer 4

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.

Answer 5

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)