Chapter 8. The class NP

The observation of the complexity classes lead to some interesting results. As we have seen in the previous chapter, . One may ask, however, whether the relation means strict subset property or there are some cases, when the two classes are equal. From the approach of practical applications, one of the most important complexity class is , since this contains the tasks, which have relatively fast solutions. Its relation to is a strongly researched area of the theory of algorithms.

First we discuss about the interpretation of the tasks from .

8.1. The witness theory

It seems to be obvious, that if one knows the solution (or some information related to the solution) of a problem, then it can be solved easier - i.e. with algorithmic approach, faster. One has to be careful, however, since solving a problem means that we are sure that the result we found is correct. Actually, the usual meaning of "solving a problem" is replaced by "proving the right solution". Thus, it is not trivial at all, which problems can be solved faster if we know some information about the solution.

For instance, if someone tells us that , then to prove the truth, we have to calculate again the multiplication. However, if we would like to know the prime decomposition of and someone tells us that , then instead of searching the decomposition, we just have to check if the relation holds and the components are primes.

The languages of can be described in a similar way. The next theorem shows that a task (language) is in , if there can be given some - not too much - information such that by this, the solution can be determined relatively fast.

Theorem (Witness Theorem) 8.1.

Let  be a language. Then the following statements are equivalent:
1. .
2. There exists a language  from  and a polynomial  such that 
 if and only if  for which  and .

Proof

The theorem stands of two statements: the first says that 1 implies 2, while the second says that 2 implies 1. Accordingly, we split the proof in two parts.

A. 1. ⇒ 2.

Since , thus there exists a nondeterministic Turing machine with polynomial time complexity such that .

Let be the time complexity of . This yields that for every there exists a computation of on , where is in accepting state and .

By the definition of the nondeterministic Turing machines, for all and we have . Let fix the order of the members of for all , i.e. assume that .

Hence, if is a computation of , then one may describe it by a sequence , where is the index of the command ( state transition ) for which is executed. Clearly for all , which means that can be represented over with at most length , where . Here . (To be more precise, one should eliminate some control symbol from to represent , thus instead of one can work with a smaller value. But this does not affect the fact, that there exists a proper constant .) The constant depends only on .

Assign to the word by , such that is the sequence of indexes corresponding to the shortest accepting computation on the input word , i.e. let . Then . Let and let .

To complete the proof we only have to show that .

Let be a deterministic Turing machine defined by .

Without precise description of , we define the set of states by and the transition function by , where is the 'th member of the set .

The Turing machine simulates the operation of . On its first tape the tape content of , while on its second tape the word can be found. During computation it reads once but not continuously. Before every steps of simulation, it reads the next component of and depending on its value executes the configuration transition, determined by on the symbol , which is read from the first tape.

Thus the Turing machine executes the computation corresponding to , i.e. it accepts exactly the words, which are from .

Its time complexity is linear, since the input word (i.e. a significant part of it, ) is read only once.

This proves the first part of the theorem.

B. 2. ⇒ 1.

Let be the Turing machine, which recognizes in polynomial time and let be the nondeterministic Turing machine, which writes a symbol and all possible words from after its input.

Define the following Turing machine:

This basically writes all possible behind the input word and tests if it is in . Since the word has length , thus the time complexity of can be determined by the following.

Let . Until the component computes, it executes steps. In the second phase during the execution of it makes at most steps. Let be the degree of and let be the degree of . Then is a polynomial, too, which has degree , thus the time complexity of the nondeterministic Turing machine is , i.e. . ✓

Remark 8.2.

1. The word  is called the witness of .
2. Theorem 8.1. sais that by the help of a witness one can check 
whether a word is in a lanaguage or not. 
Because of this property the languages from  are called 
verifiable in polynomial time.