Basic sanity check on NP-complete solutions:

Suppose there was a polynomial time solution for an NP-complete problem, but the size of NP-complete problems that could be solved is still relatively small (i.e. N = 32-64) due to limits in technology.

Would this show that P = NP? Or would this be more like the pseudo-solution that the unary subset sum is in P?

  • 13
    $\begingroup$ I don't think you understand what NP-completeness means. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Jun 8 '16 at 15:53
  • $\begingroup$ I'm referring to the common understanding of NP-Complete: a problem that is in NP and also NP-Hard. For example, Traveling Salesmen. The question restated then is: If there were a polynomial time solution for TSP for all N, yet we can currently only implement for small N (ie 30-60)...would this show P=NP. $\endgroup$ – C Shreve Jun 8 '16 at 17:26
  • 4
    $\begingroup$ " If there were a polynomial time solution for TSP for all N [...] would this show P=NP. " -- yes, almost trivially. "yet we can currently only implement for small N" -- a) What does that matter? b) What do you mean? How would you implement an algorithm that works for all N only for some? $\endgroup$ – Raphael Jun 8 '16 at 19:06
  • 8
    $\begingroup$ @CShreve $NP$-completeness doesn't require implementation. It's a mathematical fact. It has nothing to do with reality, except that we happen to live in a world where machines similar to Turing machine can be implemented and those mathematical constructs that are algorithms can be actually run on physical machines. But that's only a plus. Even in a universe where computers took exponentially more time then ours, the mathematical definitions of NP-completeness would still hold. $\endgroup$ – Bakuriu Jun 8 '16 at 20:49
  • 5
    $\begingroup$ "current technology can only implement for smallish N" -- see, that doesn't make any sense. Either you have an algorithm for all N (and P=NP) or not (and we still don't know). Whether it is practical to execute this algorithm for any N is completely irrelevant. The running time could be $10^{1000} * n^{1000}$ in whichever unit of time you want -- polynomial, but completely out of scope for any machine you can build. P=NP does not imply practical feasibility of NPC problems! That's a pop-sci myth. $\endgroup$ – Raphael Jun 8 '16 at 21:05

If you mean that the polynomial-time algorithm only works for inputs up to some fixed size, it shows nothing at all. Any problem at all (even if it's undecidable, let alone NP-complete) becomes a finite language when restricted to instances of constant size. All finite languages can be decided in constant time.

If you mean that the polynomial-time algorithm works for all inputs but it's still so inefficient that current computers can only run it on small instances then, sure, that would prove that P$\,=\,$NP. The idea that "polynomial" means "efficiently and effectively solvable" is just a short-hand. The actual definitions of P and NP don't depend on that short-hand.

  • 5
    $\begingroup$ A side note regarding undecidable problems: an undecidable problem restricted to instances of constant size is decidable in constant time. However, this does not imply that we can actually write down the algorithm to decide it. For example, the halting problem for a fixed TM is decidable by one of the constant time algorithms return true and return false, but we don't know which. $\endgroup$ – Mario Carneiro Jun 9 '16 at 5:03
  • $\begingroup$ @MarioCarneiro In many cases, "we" know which! I claim I can even give you an algorithm that solves the halting problem for infinitely many machines! The spirit of your comment is true, though: we don't necessarily know the algorithm, only its existence. $\endgroup$ – Raphael Jun 9 '16 at 17:15
  • $\begingroup$ @Raphael Yes, a small imprecision - indeed I meant that for some well-chosen fixed TMs we won't know which is the right one. Of course there are many trivial machines as well: for example return true successfully decides the halting problem for all infinitely many TMs whose initial state is halting (with other useless states). $\endgroup$ – Mario Carneiro Jun 9 '16 at 21:41
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Gilles Aug 4 '16 at 9:07

Time complexity "for small inputs" simply doesn't make sense, because the definition of time complexity is based on the limit of the running time as the input size grows to infinity.

  • $\begingroup$ @CShreve: My question is how do you define "practically implemented for small inputs"? You can't do it using the definition of time complexity, because by definition that assumes the input sizes grow arbitrarily large. Are you assuming the input sizes grow arbitrarily small? What if the algorithm takes a million years for n < 2, but less than a second for n = 2? It just doesn't make sense. It'd be dumb, but it's certainly possible to make such an algorithm. $\endgroup$ – Mehrdad Jun 9 '16 at 5:23
  • 2
    $\begingroup$ @DavidRicherby: OK, I just realized why we're at a conflict. The question I'm looking at is in the title, whereas the one you are looking at is in the body. They are not the same -- the title is asking about an algorithm which takes polynomial time for small inputs (whatever that means--my post was saying that's not meaningful), not for all inputs. The body, however, says all inputs, which I don't notice. So we're talking about different things and I don't know which was the OP's intended question. $\endgroup$ – Mehrdad Jun 9 '16 at 9:44
  • $\begingroup$ Many time complexity classes are defined in terms of asymptotics but it doesn't have to be that way. It certainly makes sense to talk about the running time being at most some specific function, for all inputs, and, indeed, you have to do that to prove things like the linear speedup theorem. $\endgroup$ – David Richerby Jun 10 '16 at 7:28

I present one possible interpretation of your question such that the answer is "YES."

Suppose that you could solve the satisfiability problem in polynomial time, but the leading term of the polynomial had a large exponent, e.g. $n^{20}$. Then it would be, indeed, the case that the solution is not practical, i.e., you can only solve the satisfiability problem on small instances using this hypothetical algorithm. Nonetheless, NP would still collapse to P. Sometimes, this exact reasoning is used to point out that the definition of P does not quite capture the notion of "practical algorithms," to which the response is that algorithms that we come up with tend to have small exponents of leading terms.

  • $\begingroup$ The way I typically describe practicality of P vs NP is that any size of input for a polynomial time algorithm (no matter how large the exponent) will eventually (some day) become practical assuming that our computational power continues to grow at an exponential rate over the years. $\endgroup$ – Paulpro Jun 9 '16 at 0:17
  • $\begingroup$ It's also well known that this isn't going to happen. All the energy in the universe cannot perform 2^256 state changes. Therefore, an algorithm taking n^256 steps will never run successfully for n > 1. $\endgroup$ – gnasher729 Jun 9 '16 at 20:04

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.