[Solved]: The initial NP-complete problem

Problem Detail: 

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 n is 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 p(n) steps.

The "P-bound NTM acceptance" problem is:

For given input string s, and a P-bound NTM T, is that T accepts s?

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 P=?NP problem.

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.

Question

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.

Asked By : Earth Engine

Answered By : Luke Mathieson

The definition of $\mathcal{NP}$ essentially immediately gives an $\mathcal{NP}$-complete problem (P-bounded NTM acceptance), what Cook and Levin gave was a proof that this automata theoretic problem could be turned into a "natural" problem (for a certain definition of natural). So mostly people are being lazy when they refer to $SAT$ as the "first" $\mathcal{NP}$-complete problem. What they mean is that it is the first not-completely-obvious $\mathcal{NP}$-complete problem.

More importantly, along with Karp's work very soon thereafter, it helped show that the class $\mathcal{NP}$ had a useful, important meaning; that it somehow "tightly" characterised a certain level of hardness of a whole raft of well known computational problems.

Some other things worth noting:

1. Cook doesn't mention $\mathcal{NP}$ at all - it had only just been invented at the time he was writing "The complexity of theorem-proving procedures". So it's only in retrospect that we recognise it as an $\mathcal{NP}$-completeness proof (admittedly, this realization took very little time - it was an exciting period for this foundational work).
2. Levin, in a strict sense, didn't even give a proof of $\mathcal{NP}$-completeness, he was working with search problems (Russians always have to show off and do it the hard way).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42547

3.2K people like this

 Download Related Notes/Documents