Complexity Classes

PDF of Prof. Santosh’s handwritten notes is here.

In the previous classes, we derived the following relations:

NTIME(t(n)) \subseteq TIME(c^{t(n)})

NSPACE(s(n)) \subseteq DSPACE(s(n)^2)

Complexity Class P

P = \{L : \exists \text{ TM that accepts L in polynomial time} \}

P = \bigcup_{k} TIME(n^k)

Examples:

  • SHORTEST-PATH = \{ (G = (V,E), D, d_{i,j} \ge 0) : \exists \text{ s-t path of length} \le D \}
    SHORTEST-PATH \in P since Dijkstra’s algorithm solves this problem in polynomial time.
  • 2-SAT \in P as it reduces to finding strongly connected components in a graph which can be done in polynomial time.

There exist decidable languages not in P.

Complexity Class NP

NP = \{L : \exists \text{ NTM that accepts L in polynomial time} \}

We say that a NTM accepts a language in polynomial time if \forall x \in L there exists an accepting path for x of length at most |x|^k.

NP = \cup_{k} NTIME(n^k)

Examples:

  • SAT = \{ F : \exists x \text{ s.t.} F(x) = 1 \}
    SAT \in NP since it is possible to guess an assignment and verify if the formula is satisfied in polynomial time.
  • CLIQUE = \{ (G = (V,E), k) : \text{ G contains a clique of size k} \}
    CLIQUE \in NP since it is possible to guess a subset of vertices of size k and verify if it forms a clique in polynomial time.

L \in NP means \exists NTM s.t. \forall x \in L, \exists an accepting path for x of length \le n^k. We could interpret the accepting path as a polynomial-sized ‘proof’ that x \in L. So, we could also define NP as the class of languages for which membership can be verified (there exists a polynomial sized certificate) by a polynomial time TM.

Does P = NP?

Clearly, P \subseteq NP

We don’t know if P = NP.

We know the following relations:

P \subseteq NP \subseteq PSPACE \subseteq EXP

From the Time hierarchy theorem, we also know P \subsetneq EXP.

Complexity Class Co-NP

Co-NP is the class of languages that are complements of languages in NP.

Examples:

  • \overline{SAT} = \{F : F \notin SAT \text{ i.e. F has no satisfying assignment} \}
  • \overline{CLIQUE} = \{ (G = (V,E), k) : \text{ G doesn't contain a clique of size k} \}

Co-NP = \{ L | \exists \text{ NTM that accepts on every path in polynomial time} \}

Unlike NP, it is unclear how to verify quickly that x \in L for languages in Co-NP. For example, it is not clear if a polynomial-sized certificate exists to show that a formula F is unsatisfiable, i.e. F \in \overline{SAT}.

Polynomial Hierarchy

In a similar manner to Co-NP, it is possible to define an entire hierarchy of complexity classes by alternating \exists and \forall quantifiers. First consider the following hierarchy of languanges based on SAT.

SAT = \{ F : \exists x F(x) = 1 \} \in NP

\overline{SAT} = \{ F : \forall x F(x) = 0 \} \in Co-NP

\Sigma_2 SAT = \{ F : \exists x \forall y F(x,y) = 1 \} \in \Sigma_2

\Pi_2 SAT = \{ F : \forall x \exists y F(x,y) = 0 \} \in \Pi_2

\Sigma_3 SAT = \{ F : \exists x \forall y \exists z F(x,y,z) = 1 \}  \in \Sigma_3

\vdots

\Sigma_i SAT = \{ F : \exists x_1 \forall x_2 \exists x_3 \dots x_i F(x_1,x_2,x_3,\dots,x_i) = 1 \} (i alternating quantifiers)

\vdots

To capture the notion of alternating quantifiers, we will define Alternating Turing Machines.

Alternating Turing Machines are NTMs except that every node is one of two types:

  • \exists type: Accepts if some path from the node accepts
  • \forall type: Accepts if all paths from the node accept

\Sigma_iTM is an ATM with i alternations starting with \exists.

\Pi_iTM is an ATM with i alternations starting with \forall.

Using the above ATMs, we could define:

\Sigma_i TIME(f(n)) = \{ L : \exists \Sigma_i \text{TM that decides L in O(f(n)) time} \}

\Pi_i TIME(f(n)) = \{ L : \exists \Pi_i \text{TM that decides L in O(f(n)) time} \}

Polynomial Hierarchy PH = \bigcup_i \bigcup_k \Sigma_i TIME(n^k) =\bigcup_i \bigcup_k \Pi_i TIME(n^k)

P \subseteq NP, Co-NP \subseteq \Sigma_2, \Pi_2 \subseteq \Sigma_3, \Pi_3 \subseteq \dots \subseteq PH

Observe that any language in the Polynomial Hierarchy can be decided by a TM using polynomial space by considering every possible combination of variables that satisfy the quantified formula. Thus, PH \subseteq PSPACE.

3 Comments

  1. if L belongs to NP, we have its complement L’ belongs to co-NP, right?
    so the NTM A that decides L in ploy-time can decide L’? (M’ accept the string that A reject…)
    so co-NP = NP…
    I don’t know which step is wrong

    Like

    Reply

    1. @Cuyaun Zhao,
      As far I understand, A NTM has a polynomial length accepting path but it says nothing about the rejecting path. Therefore we know nothing about A reject given that A is a NTM.

      Like

      Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s