Problem Detail: 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 8×8 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?
Asked By : Aceboy1993
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/56783
