文档介绍：Definition of NP
Chapter 8
NP putational
Intractability
Slides by Kevin Wayne.
Copyright © 2005 Pearson-Addison Wesley.
All rights reserved.
1
Decision Problems Definition of P
Decision problem. P. Decision problems for which there is a poly-time algorithm.
X is a set of strings.
Instance: string s.
Algorithm A solves problem X: A(s) = yes iff s
X. Problem Description Algorithm Yes No
Grade school
MULTIPLE Is x a multiple of y? 51, 17 51, 16
Polynomial time. Algorithm A runs in poly-time if for every string s, division
A(s) terminates in at most p(|s|) "steps", where p(
) is some polynomial.
RELPRIME Are x and y relatively prime? Euclid (300 BCE) 34, 39 34, 51
length of s
PRIMES Is x prime? AKS (2002) 53 51
EDIT- Is the edit distance between Dynamic niether acgggt
PRIMES: X = { 2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37, …. } DISTANCE x and y less than 5? programming neither ttttta
Algorithm. [Agrawal-Kayal-Saxena, 2002] p(|s|) = |s|8.
Is there a vector x that Gauss-Edmonds
0 1 1
4
1 0 0
1
2 4 2
,
2
1 1 1
,
1
LSOLVE
satisfies Ax = b? elimination
0 3 15
36
0 1 1
1
3 4
NP Certifiers and Certificates: Composite
Certification algorithm intuition. COMPOSITES. Given an integer s, is posite?
Certifier views things from "managerial" viewpoint.
Certifier doesn't determine whether s
X on its own; Certificate. A nontrivial factor t of s. Note that such a certificate
rather, it checks a proposed proof t that s
X. exists iff s posite. Moreover |t|
|s|.
Def. Algorithm C(s, t) is a certifier for problem X if for every string s, Certifier. boolean C(s, t) {
s
X iff there exists a string t such that C(s, t) = yes. if (t
1 or t
s)
return false
"certificate" or "witness" else if (s is a multiple of t)
return true
NP. Decision problems for which there exists a poly-time certifier. else
return false
}
C(s, t) is a poly-time algorithm and
|t|
p(|s|)