gotchaMinor
Why does restricting size of input for NP complete problem imply a runtime of O(1)?
Viewed 0 times
problemwhyimplysizeruntimeinputcompletefordoesrestricting
Problem
I've seen this statement mentioned a few times here on cs.stackexchange and have not been able to follow the logic. The statement is 'If you restrict the input size of the problem then solving that problem (even SAT) can be done in O(1)'.
So say I restrict the size of SAT to N = 1000, now that means that solving SAT for any N <= 1000 can be done in O(1)? That doesn't quite follow.
Can someone shed some light on this concept?
So say I restrict the size of SAT to N = 1000, now that means that solving SAT for any N <= 1000 can be done in O(1)? That doesn't quite follow.
Can someone shed some light on this concept?
Solution
If the input size is limited, then you can calculate the solutions to all problems. This will take a very, very, very long time. But once these solutions have been calculated, you can just lookup the solution of any problem in your list of solutions.
Even worse: Look at the definition of Big-O. The claim is that there is a constant $c > 0$, and an integer $N_0 > 0$ such that for every problem with a size $N > N_0$, the problem can be solved in less than $c * 1$ steps. If you restrict SAT to $N ≤ 1000$, then this is trivially true with $c = 1$ and $N_0 = 1001$. There are no problems with a size > 1000, therefore all the (nonexisting) problems with a size ≥ 1001 can be solved in one step.
Even worse: Look at the definition of Big-O. The claim is that there is a constant $c > 0$, and an integer $N_0 > 0$ such that for every problem with a size $N > N_0$, the problem can be solved in less than $c * 1$ steps. If you restrict SAT to $N ≤ 1000$, then this is trivially true with $c = 1$ and $N_0 = 1001$. There are no problems with a size > 1000, therefore all the (nonexisting) problems with a size ≥ 1001 can be solved in one step.
Context
StackExchange Computer Science Q#60453, answer score: 7
Revisions (0)
No revisions yet.