Essentials of P and NP

ITEC 420 - Fall 2019

• Background:

    - Polynomial time solution: O(n^k)
    - Exponential time solution: O(k^n) 

• Motivation: Discover which problems are:

    - Feasible: solve realistic problems in realistic time (ie polynomial)
    - Infeasible: solve realistic problems in unrealistic time (ie exponential) 
    - Restrict ourselves to Decidable problems only 

• Problems and languages:

    - Decision problem: Is there a path less than cost x (vs minimum cost)
      - Language: L={x:whatever} vs Problem: does whatever hold for x
    - We frequentlly don't distinguish between language and problem 

• Key Problem Classes:

    - P  = {problems that can be SOLVED  in polynomial time on a DTM}

    - NP = {problems that can be SOLVED  in polynomial time on a NDTM} 

         = {problems that can be CHECKED in polynomial time on a DTM} 
          
         - Show Venn diagram (28a slides): 
            - no known solution verifier
            - NP = known solution verifier
            - NP-P= NO known feasible solver
            - P = known feasible solver
            - NPC = Special class of NP (below)

    - Many, many real world problems fall in these two categories : see below 

• Example Problems in P - We can build polynomial time deciders for these languages:

    - PATH = { | Directed graph G has a path from s to t} (Fig 7.13)

    - RELPRIME = { | x and y are reletively prime (ie only common factor is 1}
    - L, where L is a context free language (CYK algorithm decides in n^3 time)
    - TRUE-BF = { | Boolean formula f is true with variable mapping m} 

• Example Problems in NP:

    - The best known algorithms for all of these problems/languages are exponential
    - But all have build polynomial time VERIFIERS 

    - HAMPATH = {<G,s,t> | Directed graph G has a Hamiltonian path from s to t}
        - Hamiltonian path: Visits each node once 
        - Checking a possible path (ie verifying a solution) is easy 

    - SUBSET-SUM = {<S,t> | Integer set S has a subset whose sum is t}
        - Checking (ie verifying a solution c) is easy: sum(c)=t and all c in S

    - SAT = {<f> | Boolean formula f has a mapping that makes it true}
        - Examples: 
            - P and Q and not R
            - P and Q and R
            - P and not P
            - P and (Q and not R) adn not Q

        - Checking (ie verifying a solution m) is easy

    - Traveling Salesman= {<G,c> | Graph set S tour whose cost is less than c}

• Relationship among P, NP, TD, TR, All languages

    - Clearly P <= NP < TD < TR < All
    - Clearly P is in NP
    - Unknown whether P = NP 
        - Are there any problems in NP - P? No one knows.
        - Are there polynomial solutions to problems in NP-P? No one knows.  

• Cook-Levin Theorem

    - All NP languages reduce to SAT
    - SAT is in P if and only if P = NP 
        

• NP-Complete Problems/Languages:

    - A language B is NP-Complete if it satisfies two conditions:
        1. B is in NP, and
        2. every A in NP is polynomial time reducible to B 

• Another way to prove NP-Complete

    - To show that problem Y is NP-Complete, prove that NP-Complete problem X reduces to Y
      - ie X ≤ Y
       - Think about the direction of the reduction
    

• Theorem: If B is NP-complete and B is in P, then P = NP
• Polynomial time reduction:

    - A is reducible to B if we can build a solution to A that uses B
    - eg A: find array min, B: Sort array