My lecturer made the statement

Any finite problem cannot be NP-Complete

He was talking about Sudoku's at the time saying something along the lines that for a 8x8 Sudoku there is a finite set of solutions but I can't remember exactly what he said. I wrote down the note that I've quoted but still don't really understand.

Sudoku's are NP complete if I'm not mistaken. The clique problem is also NP-Complete and if I had a 4-Clique problem is this not a finite problem that is NP-Complete?

  • $\begingroup$ What is 'finite problem'? Google and Wikipedia are not helping. $\endgroup$ – Anton Trunov Apr 29 '16 at 13:22
  • 3
    $\begingroup$ @AntonTrunov A problem in which the input has bounded length. $\endgroup$ – Yuval Filmus Apr 29 '16 at 13:37
  • $\begingroup$ @YuvalFilmus, Isn't that true of all valid Turing machine * input pairs? IIRC one of the symbols is designated the blank symbol and the input initially has a bounded region outside which symbols other than the blank symbol cannot appear. The term "NP complete" usually isn't used in the context of operations on streams which cannot be modeled without relaxing that assumption. $\endgroup$ – Mike Samuel Apr 29 '16 at 14:49
  • $\begingroup$ @MikeSamuel When I say bounded length, I mean input of size at most 100. (Or any number other than 100.) $\endgroup$ – Yuval Filmus Apr 29 '16 at 14:50
  • $\begingroup$ @YuvalFilmus, ok. I'm saying, the term "NP complete" is only used when there are no non-blank symbols on the input or there exists an integer that is the number of symbols between the leftmost non-blank symbol and the rightmost non-blank symbol. 100 would be such an example. $\endgroup$ – Mike Samuel Apr 29 '16 at 15:00

If a finite problem is NP-complete then P=NP, since every finite problem has a polynomial time algorithm (even a constant time algorithm).

When we say that Sudoku is NP-complete, we mean that a generalized version of Sudoku played on an $n^2 \times n^2$ board is NP-complete.

Finally, the 4-clique problem, while not a finite problem (the input graph has unbounded size), is an easy problem which has a polynomial time algorithm.

| cite | improve this answer | |
  • $\begingroup$ So is the 4-clique problem P since it has a polynomial time algorithm? $\endgroup$ – TheRapture87 Apr 29 '16 at 13:47
  • 1
    $\begingroup$ @Aceboy1993 Right, that's the definition of P. $\endgroup$ – Yuval Filmus Apr 29 '16 at 13:48
  • $\begingroup$ But then why is K-clique considered to be in NP-Complete? Does K not just represent a number like 4? $\endgroup$ – TheRapture87 Apr 29 '16 at 13:50
  • $\begingroup$ @Aceboy1993 No, $k$ is part of the input. For constant $k$ the problem is in P. $\endgroup$ – Yuval Filmus Apr 29 '16 at 13:51
  • $\begingroup$ Also, we can prove that Clique is NP-complete. $\endgroup$ – Yuval Filmus Apr 29 '16 at 13:52

The statement of your teacher is incorrect or probably you did not hear him correctly. The correct statement is

Any finite language $L$ with $|L| \geq 1$ cannot be NP-Complete unless $P = NP$.

That is because we still don't know (as on year 2016) if $P \neq NP$. Also $|L|>1$ is important because $\emptyset$ (the empty language) can never be NP-complete whether $P=NP$ or $P \neq NP$.

Sudoku or chess in not NP-complete (as Yuval has pointed out), because their input is finite size 9x9 or 8x8 board (I am talking about the decision versions, whether sudoku has a solution or whether chess has a winning strategy). In chess, I am assuming if you repeat a position, it is considered a draw.

| cite | improve this answer | |

Recall: A problem X is NP-complete iff it satisfies two criteria:

a) It is in NP - I.e any guessed solution of X can be verified in polynomial time.

b) It is complete for NP - I.e Every problem Y in NP has a polynomial-time reduction which translates an instance of Y to an instance of X (so that any polynomial-time program which solves X would also solve Y in polynomial-time).

We can agree that a 9x9 Sudoku satisfies (a). It is (b) where things fall down. More generally - Problems (in NP or otherwise) typically have instances of size N for arbitrarily large values of N; certainly this is true for the known problems in NP. A reduction from such a problem to one which has a maximum possible problem size couldn't possibly be a valid instance-to-instance reduction, because the former always has (infinitely) more instances than the latter. That's why Sudoku has to be generalized to NxN matrices before one can consider NP-completeness.

| cite | improve this answer | |
  • 1
    $\begingroup$ This is not correct. It's perfectly possible to have a valid reduction from a problem with infinitely many instances to a problem with finitely many instances. For example, here is a reduction from SAT to the problem of determining whether a length-1 string is equal to "a": if the SAT instance is satisfiable, map it to the string "a"; otherwise, map it to the string "b". Now, that reduction (probably) isn't computable in polynomial time but it's a perfectly valid reduction. $\endgroup$ – David Richerby Apr 29 '16 at 21:20

Your Answer

