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

In the previous classes, we derived the following relations:

**Complexity Class P**

Examples:

since Dijkstra’s algorithm solves this problem in polynomial time.- as it reduces to finding strongly connected components in a graph which can be done in polynomial time.

There exist decidable languages not in .

**Complexity Class N****P**

We say that a NTM accepts a language in polynomial time if there exists an accepting path for x of length at most .

Examples:

since it is possible to guess an assignment and verify if the formula is satisfied in polynomial time.

since it is possible to guess a subset of vertices of size and verify if it forms a clique in polynomial time.

means NTM s.t. an accepting path for of length . We could interpret the accepting path as a polynomial-sized ‘proof’ that . So, we could also define 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,

We don’t know if .

We know the following relations:

From the Time hierarchy theorem, we also know .

**Complexity Class Co-NP**

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

Examples:

Unlike , it is unclear how to verify quickly that for languages in . For example, it is not clear if a polynomial-sized certificate exists to show that a formula is unsatisfiable, i.e. .

**Polynomial Hierarchy**

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

( alternating quantifiers)

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:

- type: Accepts if some path from the node accepts
- type: Accepts if all paths from the node accept

TM is an ATM with alternations starting with .

TM is an ATM with alternations starting with .

Using the above ATMs, we could define:

Polynomial Hierarchy

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, .

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

LikeLike

@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.

LikeLike

Thanks for your reply!

LikeLike