12
$\begingroup$

Scott Aaronson has suggested that one argument in favor of $\mathsf{P} \ne \mathsf{NP}$ is that there seems to be an invisible electric fence separating $\mathsf{NP}$-complete problems from problems in $\mathsf{P}$.

I am wondering how strong this argument really is. Specifically, could there still exist some kind of invisible electric fence between the problems we currently call $\mathsf{NP}$-complete and naturally occurring problems in $\mathsf{P}$ such as linear programming or matching, even if $\mathsf{P} = \mathsf{NP}$? Naïvely, we might imagine that even if $\mathsf{P} = \mathsf{NP}$, the best algorithm for SAT (or Hamiltonian cycle, etc.) might have a running time that is a very high-degree polynomial.

I thought about this for a little, and found that it is not so easy to spell out what such an invisible fence might look like. At first I speculated that if we were to insist that our reductions between problems lie in a very low complexity class, then we might still have a small "island" surrounding SAT that is separate from the small "island" surrounding (say) linear programming. However, $\mathsf{P}$-complete problems are complete with respect to logspace reductions, and all the major $\mathsf{NP}$-complete problems are logspace-reducible to each other, so restricting reductions to be in logspace is not going to prevent the islands from coalescing. We could try replacing logspace with an even lower complexity class, but I think that even if we drop down to $\mathsf{AC}^0$, the same difficulty occurs.

There is a concept of a fine-grained reduction which at first sight looks promising. I don't know much about this subject, but I asked Virginia Vassilevska Williams, and she pointed out that there exist fine-grained reductions from SAT to "easy" problems such as edit distance. The purpose of a fine-grained reduction from problem B to problem A is to establish that if we have a better algorithm for A then we can translate that directly into a better algorithm for B; this does not preclude A from having a polynomial runtime and B from having an exponential runtime. So this is probably not the right notion for building invisible fences of the type I'm asking about.

One other idea is to try to insist that reductions run in time bounded by some fixed polynomial, say $n^3$. This is kind of ugly because of poor closure properties (e.g., the composition of two reductions won't necessarily be a reduction). But at first glance, it seems to rescue that idea that "hard" problems are those with running times that are high-degree polynomials. Can this idea be fleshed out, to construct an edifice inside $\mathsf{P}$ that resembles the usual conjectural edifice (involving the polynomial hierarchy and related complexity classes)? Or does something go wrong?

I think that either a positive or negative answer to this question would be interesting. A successful reconstruction of the usual conjectural diagram of complexity classes (complete with invisible fences) that doesn't require us to assume unproven conjectures (or at least, relies on conjectures that are significantly weaker than the "standard" conjectures) would, I think, give us more confidence that the diagram reflects some kind of real difference between different types of problems. Conversely, an argument that all the plausible reconstruction attempts are doomed to failure would provide stronger evidence that $\mathsf{P}$ really is different from $\mathsf{NP}$.

$\endgroup$
6
  • 1
    $\begingroup$ You might be interested in Vassilevska Williams & Williams paper on subcubic reductions. $\endgroup$ Feb 2, 2022 at 6:49
  • $\begingroup$ Well if reductions are restricted to a fixed polynomial time bound such as $n^{42}$, then neither NP-complete nor P-complete probems exist, and, say, $\mathrm{NTIME}(O(n))$ reduces to $\mathrm{DTIME}(O(n))$ iff $\mathrm{NTIME}(O(n))\subseteq\mathrm{DTIME}(n^{42})$. $\endgroup$ Feb 2, 2022 at 7:37
  • 2
    $\begingroup$ why DTIME(n^42) containing NTIME(O(n)) implies NTIME(O(n)) reduces to DTIME(O(n))? $\endgroup$
    – Turbo
    Feb 2, 2022 at 13:30
  • 1
    $\begingroup$ Because of a trivial padding argument: any $L\in\mathrm{DTIME}(n^{42})$ reduces in $n^{42}$ time to $L'=\{x\#1^{|x|^{42}}:x\in L\}\in\mathrm{DTIME}(n)$. $\endgroup$ Feb 2, 2022 at 18:39
  • $\begingroup$ @EmilJeřábek Good points. I'm imagining that to do what I'm envisioning, one might have to restrict attention to a specific set of "natural" problems and exclude "arbitrary" problems in (e.g.) ${\mathsf{DTIME}}(n^d)$ as well as padding. $\endgroup$ Feb 2, 2022 at 19:17

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.