P-NP Problem

Goal

Study algorithm running time - need precise model of computation. All models of computation are equivalent to each other to within a polynomial factor, with one exception: non-deterministic models, where there is exponential gap.

P/NP

Intuitive definition

\(P=\) set of every problem solvable by some deterministic algorithm in worst case^* polynomial time
\(NP =\) set of every problem solvable by some non-deterministic algorithm in polynomial time

* runtime measured as a function of the exact bit size of the input Example: bit size of integers \(\{a_1,a_2,...,a_n\}=\lg a_1 + \lg a_2 +...+\lg a_n \leq n\max\{\lg a_1,...,\lg a_n\}\)

Decision problem

Problem D where output is a single boolean value.

e.x. It there a path in a graph \(G\) ftom \(s\) to \(t\) with weight \(\leq W\)?

We will prove hardness results about decision problems, which implies hardness of corresponding optimization problems

\(D:\) the decision problem
Input: object of some type
\(Q:\) does input has property \(P\)?

Language: \(\mathcal{L}=\) set of string \(x\) that represent objects that satisfies property \(P\).
\(x\in D\): answer for \(x\) is True (yes instance), \(x\not\in D\): answer for \(x\) is False (no instance).

Formal Definition

\(P=\) the set of all decision problems solvable by some polynomial time deterministic algorithm
\(NP =\) the class of all decision problems solvable by some polynomial time verifier algorithm

Verifier (one type of non-deterministic algorithm)

Takes input \(x, c\) where \(x\) is the input of the problem and \(c\) is the certificate generated by the algorithm. - If \(x\in D\), verify \((x,c)=True\) for some \(c\)
- If \(x\not\in D\), verify \((x,c)=False\) for all \(c\)

e.x. \(COMP=\{x\in\mathbb{N}\mid x\not\in \mathcal{P}\}\).
Decision version:

Input \(x\in\mathbb{N}\)
\(Q\): Does \(x\) have factors other than 1? a.k.a. Does \(x\in COMP\)
Algorithm

for c in range(2, x): # generate
    if c | x:     # verify
        return True
    return False

More generally, generate-and-verify algorithms have the following structure - for some decision problem \(D\), input \(x\) for \(D\) - Generate all possible "certificates" \(c\) - verify input \(x\) with the help of each \(c\) if verified then return True, else return False. (verifier)

\(D\in NP\) IFF \(\exists\) verifier for \(D\) thats run in polynomial time, ignoring the time taken to generate all possible certificate.

For \(COMP\):

verify(x,c)

return x mod c == 0

will not take constant time for large input. Basic arithmetic operations are polynomial time. Therefore verify is polynomial time (as a function of \(\log x\))

Example: Vertex cover

input \(G=(V,E)\) undirected and \(k\in\mathbb{N}\)
output: Does \(G\) contain a vertex cover \(S. |S|=k\) where \(S\subseteq V\) every edge has \(\geq 1\) on endpoints in \(S\)

Claim: \(D\in NP\)
Describe a verifier:

verify(G,k,C)

# c is a subset of V with |c|=k
return every edge has one endpoint in c

runtime is \(O(|E|k)\in O(|V||E|)\) - if \((G,k)\in D\), \(verify(G,k,c)=True\) when c is a vertex cover. - conversely, if \(verify(G,k,c)=True\) for some \(c\), then \(c\) is a vertex cover of size \(k\) Then \((G,k)\in D\)

Note that generally, continue of verify must be polynomial as a function of size(x) only (ignoring c)

coNP

Example Dense
Input: \(G=(V,E)\) undirected, \(k\in\mathbb{N}\)
Output: Does every subset of \(k\) vertices contains at least one edge?

When answer is yes, no easy way to verify.
When answer is no, verifier

verify(G,k,c)

if c is a subset of k vertices:
    return not G contains none of the choose(k,2) edges between vetex of c

\((G,k)\in Dense\) IFF \(\not\exists c, verify(G,k,c)=False\)

\(coNP\) = the set of decision problems whose no-instance can be verified in polynomial time

every coNP question's negation is NP question.

Believe \(P\neq NP\), which there are problems that can be verified in polynomial time but cannot be answered in \(O\). But no proof

Question

Given \(D\in NP\), how to show \(D\not\in P\), likely.

Intuitively, compare the difficulty of solving problems to find hard problems in \(NP\).

Reducible

For any two decision problems \(D_1,D_2\), let \(i_j=\) the set of all inputs to \(D_j\) (yes and no instance). We say \(D_1\) is polynomial reducible to \(D_2, (D_1\rightarrow_p D_2)\) IFF \(\exists f:I_1\rightarrow I_2\) s.t. \(f\) computable in polynomial time and \(\forall x\in I_1, x\in D_1\) IFF \(f(x)\in D_2\)

Example

independent set \(\rightarrow_p\) Vector Cover
independent set: given \(G,k\), does \(G\) contains an independent set of size \(k\)
vertex cover: given \(G,k\), does \(G\) contains a vertex cover of size \(k\).

Define \(f\):

reduce(G,k)

# G,k input for indep set
return (G, |V|-k)

Show \(\forall x\in I_1, x\in D_1\) IFF \(f(x)\in D_2\)

If \(S\subseteq V\) independent set, \(|S|=k\), then \(V-S\) is a vertex cover in \(G\). If \(S\subseteq V\) vertex cover, \(|S|-n-k\), then \(V-S\) is a indep set in \(G\).

Example Questions

Show UP\(\in P\) where input \(11..1\) is \(n\) 1's. Output \(n\) is prime.
Different from normal algorithm that returns whether a number is prime. The input size is \(n\) instead of \(\log m\) where \(m\) is the value of the number.
Show \(Triangle\in P\) where input \(G\) undirected output whether exists a triangle.
There are \({n\choose 3}=n(n-1)(n-2)/6\) combinations of vertices and check edges take constant time.
Show Clique\(\in NP\) where input \(G\) undirected, \(k\in\mathbb{Z}^+\) output whether exists a \(k\)-clique (\(k\) vertices with all edges) in \(G\).
Given a certificate as \(C\subseteq V\). return \(|C|=k\land \forall u,v\in C, (u,v)\in E\). Obviously can be verified in polytime \((O(n^2))\). If \(G,k\in Clique\) then \(\exists C\). If \(\exists C\) then \(G,k\in Clique\).
SS\(\in NP\) where input \(S\) be a set of positive integers, \(t\in\mathbb{Z}^+\) output \(S'\subseteq S. \sum S = t\)
Given a certificate as \(S'\) return \(S'\subseteq S\land \sum S'=t\)