It is always claimed that Cook and Levin gives the very first NP-complete problem and proof of it.
But when I look at the actual proof I think what Cook and Levin did was reduced (or transformed) SAT to "P-bound NTM acceptance" problem.
Formally, we define
A P-bound NTM is a non-deterministic Turing machine that was given a polynomial expression
p(n)associate with it, such that if
nis the size of the input string, and it accepts the string iff there is an execution sequence the NTM halt at an final state within
The "P-bound NTM acceptance" problem is:
For given input string
s, and a P-bound NTM
T, is that
So if I understand right, what Cook presented in his proof is
Given an instance of P-bound NTM acceptance, there is a polynomial reduction/translation that convert this instance into an instance of SAT. (P-bound NTM acceptance reduce to SAT)
with this and an easier fact that
Every instance of NP problems can be reduced into an instance of P-bound NTM acceptance. (P-bound NTM acceptance is NP-hard)
lead us to the conclusion : SAT is both NP-hard and in NP, so it is NP-complete
But in addition to that we can also see
P-bound NTM acceptance can be resolved with an NTM within polynomial time. (P-bound NTM acceptance is in NP)
This should be straight forward. The only thing to worry about is we are simulating an NTM so we need to think about the guessing staff. Fortunately we are also defining an NTM, so what we actually need is a non-deterministic universal Turing machine.
Running this machine would not require more than polynomial additional time.
According to this we have
P-bound NTM acceptance is NP-complete.
I am not to disregard Cook/Levin's work, instead, their work is still very important and historical as they finished the first NP-complete proof.
However if I were right would it open some another view of the NP-complete problems? If we use other computation model for example, the "P-bound NTM acceptance" will be different, and if some clever computation model was invented we could be able to use this result to solve
Also I think if we see P-bound NTM acceptance instead of SAT as the first (or zeroth?) NP-complete problem it would help people understand the proof of Cook-Levin's proof.
Given that every existing proof of NP-complete results is actually through it (yes, they are going through SAT, and SAT going through it), is this a natural, intuitive view that "P-bound NTM acceptance" is the ultimate initial NP-complete problem?
Is this only a matter of defintion
A comment suggests this is "P-bound NTM acceptance" is the definition of NP.
The definition of NP is (Skudkamp, Languages and Machines edition 3, Def 15.2.2)
A language L is said to be accepted in nondeterministic polynomial time if there is a nondeterministic Turing machine $M$ that accepts L within $tc_M \in O(n^r)$, where $r$ is a natural number independent of $n$. The family of languages accepted in nondeterministic polynomial time is denoted $NP$.
So the problem "Is language $L \in NP$"? is defined as
Is there a nondeterministic Turing machine $M$ that accepts L within $tc_M \in O(n^r)$, where $r$ is a natural number independent of $n$?
This is not exactly the same as "P-bound NTM acceptance".
In general, the
f(n) bound TM acceptance problem is not in complexity
O(f(n)). Although it is true that you can always simulate the TM within
f(n) steps, but the simulation will introduce additional work, not just to decode the machine and simulation its action, but also the need to check the simulation steps is actually within the bound.
This increases the time complexity, and it is not trivial in general. See time hierachy theorems, there is a proof of "there are languages can be accepted in O(n^2) but not in O(n)" based on this argument.
It is true that "P-bound NTM acceptance" is in NP simply because those additional work can be done in P time.
It is to know that this "P-bound NTM acceptance is in NP" is also implied by Cook's theorem because SAT is in NP and PNA reduces to it. However, a direct proof is also straight forward.