patternModerate
Can any finite problem be in NP-Complete?
Viewed 0 times
problemcanfiniteanycomplete
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#56783, answer score: 15
Revisions (0)
No revisions yet.