1
$\begingroup$

If $P=NP$ was proven with an algorithm, would that have to mean that there is one algorithm that has to work for all inputs of length $n$?

More specifically, what if there were infinitely many polynomial time algorithms for $n=1,2,3,...$, but no algorithm would work for more than one value $k=n$. I don't mean that $n$ would be fixed, but that for each greater $n$ we would have to modify or construct a new algorithm that solves the problem in polynomial time.

I am thankful for any answers :)

$\endgroup$
3
$\begingroup$

I'll start with your first question:

If $P=NP$ was proven with an algorithm, would that have to mean that there is one algorithm that has to work for all inputs of length $n$?

Yes, in order for $P$ to equal $NP$, there has to be one algorithm for all inputs. It can't be infinitely many algorithms that each solve some subset of the problem.

For your more specific question, though, you may be surprised: we already do have an algorithm that solves SAT for each specific value of $n$ and runs in polynomial time! In fact, we have an algorithm for each specific $n$ that works in constant time. Take $n = 3$, for example. Then just write out all the possible inputs of length $3$, and make a table of all the answers for each input. The algorithm just looks at the input, queries the table, and returns the result:

$$ \begin{array}{cc} \text{input} & \text{answer} \\ 000 & 0 \\ 001 & 1 \\ 010 & 1 \\ 011 & 0 \\ \cdots \end{array} \\ \text{Algorithm: on input $x$ of length 3, return the answer given in the above table.} $$

What went wrong here? The problem lies in what we mean by polynomial time. Hidden in the word "polynomial" is that we usually mean polynomial in $n$, i.e. it has to run in time that is a polynomial function of the input length. If the input length is a fixed constant, then it no longer makes sense to ask for a polynomial time algorithm: all algorithms (no matter how fast or slow) will be polynomial time since there are only finitely many possible inputs we care about, so the running time is always bounded by a constant.


Addendum. You raise an interesting question in the comments. My initial interpretation of it was, what if we require that the algorithm for each $n$ runs in a fixed polynomial $p(n)$ (so the polynomial upper bound has to be the same for every $n$)? To this the answer is still that we can already do this, because we can hardcode the table in the program so that it runs in exactly $n$ steps (the time to read the input). Think of it as the following program:

ANSWER_TABLE = [000: 0, 001: 1, 010: 1, 011: 0, ...]
On input x:
  return ANSWER_TABLE[x]

Now the program size is $2^n$, sure, but the program runs in time $n$. You could also explicitly write out a giant set of nested if-then-elses instead of hardcoding the table. Anyway, we have an algorithm for each $n$ that solves SAT and runs in at most $n$ steps.

But you still would object that the program size is still exponential in $n$. If you also require that the program itself has size polynomial in $n$, then I am not sure if it is possible anymore. That may be related to the field of circuit complexity.

$\endgroup$
16
  • 2
    $\begingroup$ Okay, I get that the definition of polynomial time makes a fixed n useless, but in your example the table is very large. If there were smaller tables, polynomially sized ones, what would that imply? Thanks for your answer, really made it clear. $\endgroup$
    – user136613
    Aug 27 '21 at 0:41
  • $\begingroup$ @Dude The table is large, but it can be hardcoded in the program. Because the table is hardcoded, all it takes to run the program is to read the input ($n$ steps) and immediately output the answer. So it is polynomially sized independent of $n$. I'll clarify this. $\endgroup$
    – 6005
    Aug 27 '21 at 5:35
  • $\begingroup$ I added some thoughts. $\endgroup$
    – 6005
    Aug 27 '21 at 5:46
  • $\begingroup$ Thanks for the additional thoughts on this! I am still wondering if it is possible. I think in the end my question is about data compression then, but I also read somewhere that you cannot compress random data? So if we want to do it for any input bits then it shouldn't be possible?.. Probably, I am missing many things on that topic. $\endgroup$
    – user136613
    Aug 27 '21 at 11:07
  • 1
    $\begingroup$ Yes, but to satisfy all inputs we would need a program that is made for an infinite big input length. I agree there is something wrong in my reasoning. Thanks for the answers though, I will maybe ask this question later as a new thread, if I don't find my errors. $\endgroup$
    – user136613
    Aug 28 '21 at 11:39

Your Answer

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