<p>Scott Aaronson has suggested that one argument in favor of <span class="math-container">$\mathsf{P} \ne \mathsf{NP}$</span> is that there seems to be an <a href="https://scottaaronson.blog/?p=1720" rel="noreferrer">invisible electric fence</a> separating <span class="math-container">$\mathsf{NP}$</span>-complete problems from problems in <span class="math-container">$\mathsf{P}$</span>.</p>
<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 <span class="math-container">$\mathsf{NP}$</span>-complete and naturally occurring problems in <span class="math-container">$\mathsf{P}$</span> such as linear programming or matching, even if <span class="math-container">$\mathsf{P} = \mathsf{NP}$</span>? Naïvely, we might imagine that even if <span class="math-container">$\mathsf{P} = \mathsf{NP}$</span>, the best algorithm for SAT (or Hamiltonian cycle, etc.) might have a running time that is a very high-degree polynomial.</p>
<p>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 &quot;island&quot; surrounding SAT that is separate from the small &quot;island&quot; surrounding (say) linear programming.  However, <span class="math-container">$\mathsf{P}$</span>-complete problems are complete with respect to logspace reductions, and all the major <span class="math-container">$\mathsf{NP}$</span>-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 <span class="math-container">$\mathsf{AC}^0$</span>, the same difficulty occurs.</p>
<p>There is a concept of a <a href="https://en.wikipedia.org/wiki/Fine-grained_reduction" rel="noreferrer">fine-grained reduction</a> 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 &quot;easy&quot; 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.</p>
<p>One other idea is to try to insist that reductions run in time bounded by some fixed polynomial, say <span class="math-container">$n^3$</span>. 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 &quot;hard&quot; problems are those with running times that are high-degree polynomials.  Can this idea be fleshed out, to construct an edifice inside <span class="math-container">$\mathsf{P}$</span> that resembles the usual conjectural edifice (involving the polynomial hierarchy and related complexity classes)?  Or does something go wrong?</p>
<p>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 &quot;standard&quot; 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 <span class="math-container">$\mathsf{P}$</span> really is different from <span class="math-container">$\mathsf{NP}$</span>.</p>

CC BY-SA 4.0
2022-02-02T06:49:19.370Z
You might be interested in Vassilevska Williams & Williams paper on subcubic reductions.
Joshua Grochow
CC BY-SA 4.0
2022-02-02T07:37:30.337Z
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})$.
Emil Jeřábek
CC BY-SA 4.0
2022-02-02T13:30:40.790Z
why DTIME(n^42) containing NTIME(O(n)) implies NTIME(O(n)) reduces to DTIME(O(n))?
Turbo
CC BY-SA 4.0
2022-02-02T18:39:15.603Z
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)$.
Emil Jeřábek
CC BY-SA 4.0
2022-02-02T19:17:01.510Z
@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.
Timothy Chow
CC BY-SA 4.0
2022-02-12T14:37:34.307Z
I think the "fence" might be conceptual rather than computational. It might be the case that the reductions are so complex conceptually that they are beyond our reach. One can try to cast this as provability in particular theories, but I don't think that captures conceptual notion of complexity for human understanding.
Kaveh
<cc.complexity-theory><reductions><p-vs-np>
Invisible electric fence even if P = NP?
Timothy Chow
# Invisible electric fence even if P = NP?

(Asked by: username_0 on 2022-02-02)

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](https://scottaaronson.blog/?p=1720) 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](https://en.wikipedia.org/wiki/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}$.

**Tags:** cc.complexity-theory, reductions, p-vs-np
> **Comments:**
> **username_1**: You might be interested in Vassilevska Williams & Williams paper on subcubic reductions.  
> **username_2**: 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})$.  
> **username_3**: why DTIME(n^42) containing NTIME(O(n)) implies NTIME(O(n)) reduces to DTIME(O(n))?  
> **username_2**: 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)$.  
> **username_0**: @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.  
> **username_4**: I think the "fence" might be conceptual rather than computational. It might be the case that the reductions are so complex conceptually that they are beyond our reach. One can try to cast this as provability in particular theories, but I don't think that captures conceptual notion of complexity for human understanding.  

---

## 0 answers

