1
$\begingroup$

Suppose we had an algorithm that solved an NP-complete problem (SAT, TSP, etc.) in time $O(2^{N/B})$ where $B>2$ is an input to the algorithm, along with the instance to be solved.

So for $B < N$, we have a reduced exponential growth runtime, but for $B \geq N$ we actually have a constant runtime.

What would this say about P vs NP? Does this complexity class already exist or would it be a new one? Would this add anything significant to our current understanding of complexity theory?

$\endgroup$
  • $\begingroup$ "What would this say about P vs NP? " -- nothing, I guess. $\endgroup$ – Raphael Jun 22 '16 at 16:50
  • 1
    $\begingroup$ I don't understand. How do you propose to have an algorithm whose performance gets better as some input increases in value? Why would anyone call your algorithm as solvesat(phi,2) and wait time $2^{n/2}$ for an answer when they could just call it as solvesat(phi,length(phi)) and receive the answer instantly? Indeed, an algorithm with that property cannot exist, since we know that SAT cannot be solved in constant time. $\endgroup$ – David Richerby Jun 22 '16 at 17:35
  • $\begingroup$ It is my understanding that there is no proof that SAT cannot be solved in constant time. Moreover, that is what this algorithm would suggest...that for B=N, SAT is solved in constant time. $\endgroup$ – C Shreve Jun 22 '16 at 17:55
  • 1
    $\begingroup$ @CShreve That proof is trivial by a standard adversary argument. $\endgroup$ – Raphael Jun 22 '16 at 18:37
  • $\begingroup$ It won't say anything about P vs NP, but if such algorithm exist this means Exponential Time Hypothesis(ETH) is not true and many of the proven lower bounds for many problems assuming ETH holds will no longer be lower bounds. $\endgroup$ – Thinking Jun 23 '16 at 9:12
6
$\begingroup$

It says nothing about the P vs NP question because no such algorithm can exist. If there is an algorithm that takes as its input a formula $\phi$ and an integer $B$ and determines whether $\phi$ is satisfiable in time $O(2^{N/B})$, where $N$ is the length of $\phi$, then we can decide SAT in constant time by calling the algorithm with $B=N$.

But we know that SAT cannot be solved in constant time because, in $k$ steps of the computation, you can only read the first $k$ characters of the input. That means that you have no way of distinguishing between the formulas $X\land X\land\dots \land X$ and $X\land X\land\dots \land X\land\neg X$, where $X$ is repeated, say, $k$ times. One of these formulas is satisfiable and the other isn't, but an algorithm running in $k$ steps would have to return "satisfiable" or "unsatisfiable" before seeing the $\neg X$ (or lack of it) at the end.

$\endgroup$
  • 1
    $\begingroup$ To clarify - you're saying that solving SAT must take at least N steps...simply to read in the input correct? $\endgroup$ – C Shreve Jun 22 '16 at 20:58
  • 1
    $\begingroup$ @CShreve Exactly. Only very simple languages can be solved in constant time: finite and co-finite languages (co-finite = complement of finite), languages of the form $\{xy\mid x\in L, y\in\Sigma^*\}$ where $L$ is finite or co-finite, and unions of any of these. (Plus maybe some others that I've missed.) $\endgroup$ – David Richerby Jun 22 '16 at 21:21
0
$\begingroup$

So, basically, you're asking about a hypothetical $O((1+\epsilon)^N)$ 3-SAT algorithm where $\epsilon$ can be as small as desired. (Because $2^{\frac{N}{B}} = (2^{\frac{1}{B}})^N = (1+\epsilon)^N$ via setting $\epsilon$ to $1-2^\frac{1}{B}$.)

Such an algorithm wouldn't resolve the $\text{P} =^? \text{NP}$ problem. It doesn't solve 3SAT in polynomial time, and it doesn't demonstrate that no algorithm can solve 3SAT in polynomial time.

However, it would disprove the exponential time hypothesis, which conjectures that 3SAT costs at least $2^{\Omega(n)}$ (i.e. $\Omega((1+c)^{n})$ for some constant $c > 0$). It would be a big deal.

$\endgroup$
  • $\begingroup$ Also to be explicit, if it could be shown that 3SAT could be solved in (choose B = 8 for example)...O(2^(N/8)) this would prove quicker then the current best algorithm which I believe solves 3SAT in roughly 2^N/3 would it not? $\endgroup$ – C Shreve Jun 22 '16 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.