notas.itmens
P and NP
The classes \(\mathbf{P}\) and \(\mathbf{NP}\)#
Definitions:
- \(\mathbf{P}\) is the class of decision problems that are solvable in polynomial time.
- \(\mathbf{NP}\) is the class of search problems that satisfies the following property: there is a polynomial time algorithm that, given \(x,y\), decides whether \((x,y)\in R\) for the relation \(R\) that specifies the search problem (efficiently computable), and there is a polynomial \(p\) s.t. if \((x,y)\in R\) then \(|y|\leq p(|x|)\) (the solution is of polynomial length).
The definition for \(\mathbf{NP}\) can be converted to the class of decision problems: the decision problem specified by the language \(L\) is in the class \(\mathbf{NP}\) if (definition) there is some \(\mathbf{NP}\) relation \(R\) s.t. \(x\in L\) iff there is an \(y\) s.t. \((x,y)\in R\). More precisely
A language \(L\) is in \(\mathbf{N}\), if (definition), there exists a polynomial \(p:\mathbb{N}\to\mathbb{N}\) and a polynomial time Turing machine \(V\) (the verifier for \(L\)) s.t. for every \(x\in\{0,1\}^\ast\),
The \(u\) is called a certificate or a witness for \(x\) with respect to the language \(L\) and the verifier \(V\).
This shows that if a problem is in \(\mathbf{NP}\) it means that it is easy to verify. And it does not mean it is hard to compute (though it doesn't mean, as far as we know, it is easy to compute, either).
Clearly \(\mathbf{P}\subseteq \mathbf{NP}\) since \(p(|x|)\) is allowed to be \(0\) (\(u\) an empty string). The problem is whether \(\mathbf{NP}\subseteq \mathbf{P}\), namely, whether the deterministic and nondeterministic Turing machines have the same efficient capacity. This is the \(\mathbf{P}\) versus \(\mathbf{NP}\) problem.
Equivalently:
- \(\mathbf{P} = \bigcup_k \text{DTIME}(n^k)\).
- \(\mathbf{NP} = \bigcup_k \text{NDTIME}(n^k)\), which is a corollary of
- \(\mathbf{NP}\) is the set of decision problems that are solvable in polynomial time by a non-deterministic Turing machine (almost by definition).
\(\mathbf{NP}\)-completeness#
We say that a language \(L\) is
- \(\mathbf{NP}\)-hard if (definition) \(L' \leq_q L\) for every \(L'\in \mathbf{NP}\).
- \(\mathbf{NP}\)-complete if (definition) \(L\) is \(\mathbf{NP}\)-hard and \(L\in\mathbf{NP}\).
Surprisingly large number of \(\mathbf{NP}\) problems turned out to be \(\mathbf{NP}\)-complete. Conjecture that \(\mathbf{NP}\setminus \mathbf{P}\) consists of \(\mathbf{NP}\)-complete problems. If \(\mathbf{P}=\mathbf{NP}\), then this is trivially true. It turned out, however, that for \(\mathbf{P}\neq \mathbf{NP}\), the conjecture is not true.
Ladner's theorem#
Theorem. Suppose that \(\mathbf{P}\neq\mathbf{NP}\), then there exists a language \(L\in \mathbf{NP}\setminus \mathbf{P}\) that is not \(\mathbf{NP}\)-complete.
Time Hierarchy Theorem(s)#
Time constructible function#
Definition. A function \(f:\mathbb{N}\to\mathbb{N}\) is time constructible if there is an algorithm that, on input \(n\), computes the value \(f(n)\) in time \(O(f(n))\).
One needs to work quite hard to come with an example of a function that is not time constructible. All polynomial functions, exponentials, root functions, and their combinations are time constructible. One example of non time constructible function: Let \(f(n)\) be \(n^2\) if the number \(n\) written in binary encodes a Turing machine that halts on all inputs, be \(n^2 + 1\) otherwise.
The following theorems are proved by diagonalization (mod some technical subtleties).
Time Hierarchy Theorem#
Theorem. If \(f,g\) are time constructible functions that satisfy \(f(n)\log f(n) = o(g(n))\), then
\[\text{DTIME}(f(n))\subsetneq \text{DTIME}(g(n)).\]Now \(f,g\) are time constructible functions, hence there is an algorithm such that the value of \(f(n)\) asymptotically bounds the time needed to compute the value itself. So if the time that bounds the computation of \(f(n)\) (more precisely \(f(n)\log f(n)\)) is dominated by that bounds \(g(n)\) (i.e. needs more time to compute \(g(n)\)), then the class of decidable problems in the former class is strictly included by the latter class. Which basically means that allowing Turing machines more computation time strictly increases the set of languages that they can decide.
Equivalently, given a time constructible function \(f\),
\[\text{DTIME}(o(f(n)) \subsetneq \text{DTIME}(f(n)\log f(n)).\]Nondeterministic Time Hierarchy Theorem#
Theorem. If \(f,g\) are time constructible functions that satisfy \(f(n+1)=o(g(n))\), then
\[\text{NDTIME}(f(n))\subsetneq \text{NDTIME}(g(n)).\]“Diagonalization” cannot determine P vs NP#
By “diagonalization” it is meant that any technique that relies solely upon the following properties of Turing machines:
- The existence of an effective representation of Turing machines by strings.
- The ability of one Turing machine to simulate any another wihout much overhead in running time or space.
The Turing machines then are used as black boxes: the machine's internal workings do not matter. Hence oracle Turing machines can be used without altering the argument, and regardless of what the oracle \(O\) is.
In other words, any result about Turing machines or complexity classes that only uses the above two properties also holds for the set of all Turing machines with oracle \(O\), such results are called relativizing results.
Let \(\mathbf{P}^O\) denote the class \(\mathbf{P}\), but with the Turing machines having access to the oracle \(O\). Similar for \(\mathbf{NP}^O\).
Theorem. There exist oracles \(A, B\), s.t. \(\mathbf{P}^A = \mathbf{NP}^A\) and \(\mathbf{P}^B\neq \mathbf{NP}^B\).
Meaning that none of the \(\mathbf{P} = \mathbf{NP}\) or \(\mathbf{P}\neq\mathbf{NP}\) can be a relativizing result, regardless of which being true. To resolve \(\mathbf{P}\) vs \(\mathbf{NP}\), then one has to use some fact about Turing machines that does not hold in presence of oracles.
Note that this is very similar to independence results, only that the independence is based upon restricting the proof to known techniques. In an unpublished manuscript AIV93(S. Arora, R. Impagliazzo, and U. Vazirani. Relativizing versus nonrelativizing techniques: The role of local checkability) an axiomatic system is developed so that what constitutes as “known techniques” is made clear.
Some more complexity classes#
- The class \(\mathbf{E} = \text{DTIME}(2^n)\).
- The class \(\mathbf{EXP} = \bigcup_k\text{DTIME}(2^{n^k})\).