2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think that's true by definition. $\endgroup$ – Albert Hendriks May 14 '15 at 12:34
  • $\begingroup$ in some other sense there seems to be no "ultimate" NP complete problem, they cannot be discriminated from each other by any natural criteria. what you call "P-bound NTM acceptance" is the defn of the class NP. $\endgroup$ – vzn May 14 '15 at 15:39
  • $\begingroup$ "what Cook and Levin did was reduced (or transformed) SAT to 'P-bound NTM acceptance' problem." The other way around: you prove that SAT is NP-complete by reducing arbitrary NP-problems to SAT. $\endgroup$ – David Richerby May 16 '15 at 12:14
  • 1
    $\begingroup$ This question is long and rambling to the extent that I can't actually tell what the real question is. Adding an extra ten paragraphs in response to a comment suggests that you're really looking for somewhere you can discuss the issue, rather than asking a question per se. Stack Exchange isn't appropriate for discussion: it's a question-and-answer site and it doesn't support back-and-forth. Since you have enough reputation to use Computer Science Chat, I suggest you ask about it there. $\endgroup$ – David Richerby May 16 '15 at 12:17
3
$\begingroup$

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).
$\endgroup$
  • $\begingroup$ The reason I ask the question is that textbooks usually contains discussion why we cannot assume the set "NP-complete" languages is non-empty until Cook gives his proof, without stating the history background. On the other hand, by modern definition, the existence of a NP-complete language is obvious. $\endgroup$ – Earth Engine May 16 '15 at 14:00
  • $\begingroup$ @EarthEngine, I agree, it's pretty obvious from the definition that something is $\mathcal{NP}$-complete, it's not obvious that something interesting is though, but the texts are a bit disingenuous. $\endgroup$ – Luke Mathieson May 18 '15 at 2:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.