Essentials of P and NP - ITEC 420 - Fall 2010
---------------------------------------------
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)
Key Problem Classes:
- P = {problems that can be SOLVED in polynomial time on a DTM}
- NP = {problems that can be CHECKED in polynomial time on a DTM} (Def 7.19)
= {problems that can be SOLVED in polynomial time on a NTM} (Th 7.20)
= {problems that can be SOLVED in exponential time on a DTM} (Th 7.11)
- Th 7.11 (roughly): A problem that can be solved in t(n) time on a
NTM can be solved in 2^O(t(n)) time on a DTM.
- Many, many real world problems fall in these two categories
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}
Problems as languages:
- we cast problems as languages for analysis
- we interchange language and problem freely
Example Problems in NP:
- The best known algorithms for all of these problems/languages are exponential
- But all have build polynomial time VERIFIERS
- HAMPATH = { | Directed graph G has a Hamiltonian path from s to t}
- Hamiltonian path: Visits each node once (Fig 7.17)
- Checking a possible path (ie verifying a solution) is easy
- SUBSET-SUM = {~~ | 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-BF = { | Boolean formula f has a mapping that makes it true}
- Checking (ie verifying a solution m) is easy: Is in TRUE-BF
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 (Th 7.27):
- SAT-BF 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
Theorem 7.35: 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
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
~~