P and NP


Date: 2021-04-01


title: 'P and NP' date: '2021-04-01'

Time Complexity

Idea: Does Nondeterminism (Magic) help?

P and NP

Def: P is the class of languages that are decidable in polynomial time on a deterministic Turing Machine. Easy for Authur

Def: NP is the class of languages that are decidable in polynomial time on a nondeterministic Turing Machine. Easy for Merlin Alternative: NP is the class of languages whose YES instances can be verified by Authur in polynomial time.

Def: coNP is the class of languages - whose complements are in NP - whose NO instances can be verified by Arthur in polynomial time Theorem: Proof: if be a language of , by switching accept and reject states, we get a deterministic TM that decides .

Question: Is matching problem in P? (Yes but it's shown in CS260...)

  • Matching By a NTM: for each knight
    1. Check that they are only matched to one task
    2. Check that the task they are matched to is on their list
    3. Check that the task they are matched to is not matched by any other knight
  • Matching (by Hall's Theorem)

Is P = NP? (Does Arthur need Merlin?) We don't know.

Def: A problem is NP-Hard (actually hard for Arthur) if .

Def: A problem is NP-Complete if both and is NP-Hard.

Theorem (Hall's Theorem): Let be a bipartite graph with bipartition () and . Then contains a perfect matching if and only if for all . Proof: () By Pigeonhole principle () Suppose for all , but does not have a perfect matching.

Alternating path: every other edge is contained in Augmenting path: alternating path in which first and last edges are unmatched

Let be the maximum cardinality matching in , and let be unmathced in . Let . Lemma: matches perfectly with . The alternating paths reach along edges not in and reach along edges in

...

  1. Initialize . // Empty matching.
  2. Assert: is a matching in .
  3. If saturates all vertices of , then return the X-perfect matching
  4. Let be an unmatched vertex (a vertex in ).
  5. Using the Hall violator algorithm (), find either a Hall violator or an -augmenting path.
  6. In the first case, return the Hall violator.
  7. In the second case, use the M-augmenting path to increase the size of M (by one edge), and go back to step 2. At each iteration, M grows by one edge.

Theorem:

NP Problems

is in NP The following is a verifier for : On input <<>, >:

  1. Test whether is a subgraph with nodes in
  2. Test whether contains all edges connecting nodes in
  3. Both pass, accept; otherwise reject

The Cook-Levin Theorem

A boolean formula is satisfiable if there is at least one "T" row in the truth table.

Theorem: is NP-Complete: If , then .

Suppose . Let N be a NTM that decides in time. Convert N's computation to boolean formula that is satisfiable iff there is an accepting computation for N. Represent the accepting computation as a tableu an of all configurations of from start to acceptance.

Construct formula to represent N's accepting computation where variable .

is true iff one variable is turned on per cell is true iff the first configuration is a start configuration is true iff somewhere appears in one of the cells Finally, guarantees each row of the tableau corresponds to a configuration that legally follows the preceding row according to N's transition function, by maintaining a valid "window"

Need to review...

The whole NP-Hard, NP-Complete...

  • Is ? We don't know
  • Prove easy for Arthur
  • Prove easy for Merlin
  • Prove hard for Arthur
  • Prove easy for Merlin and hard for Arthur

© 2022 Yuk Yeung Lam. All Rights Reserved.