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