Problem vs. language Polynomial time a decision problem Q can be regarded as a polynomial time by an algorithm A if A anguage L accepts every binary string in L in polynomial L={x∈Σ:Q(x=1} time无法保证非L中的语言在多项式时间内 被拒绝] A language accepted by an algorithm a is L={x∈{0,1}:A(x=1 We say that a language is decided in polynomial time by an algorithm a if A A language decided by an algorithm A if it ccepts every binary string in L in polynomial accepts all string x with A(x)=I and rejected time, and rejects in polynomial time the string all string x with A(x=0 not in L 清华大学宋域恒 请华大学宋恒 class p的另一个等价定义 Polynomial time verifications P=(Lc 10, 11*: there exists an algorithm A Verification algorithm a is a two arguments that decides L in polynomial time) algorithm where one argument is an nd the other binary string y called a certificate A two arguments algorithm A verify input x if there exists a certificate y 清华大学末斌恒 请华大学宋恒 Language defined by verification NP的一个等价定义 L=(x in (0, 1): there exists y in (0, 1) A language L belongs to NP if and only if such that A(x, y)1g here exists a two-input polynomial-time algorithm A and a constant c such that L=(x in ( 0, 1;": there exists y in (0, 1)with lyO(xl)such that A(x, yl We say that algorithm A verifies language L 清华大学末破恒 请华大学宋 66 清华大学 宋斌恒 31 Problem vs. language • A decision problem Q can be regarded as a language L: – L={x∈Σ∗ : Q(x)=1} • A language accepted by an algorithm A is – L={x∈{0,1}∗ : A(x)=1} • A language decided by an algorithm A if it accepts all string x with A(x)=1 and rejected all string x with A(x)=0 清华大学 宋斌恒 32 Polynomial time • We say that a language is accepted in polynomial time by an algorithm A if A accepts every binary string in L in polynomial time[无法保证非L中的语言在多项式时间内 被拒绝] • We say that a language is decided in polynomial time by an algorithm A if A accepts every binary string in L in polynomial time, and rejects in polynomial time the string not in L 清华大学 宋斌恒 33 class P的另一个等价定义 • P={L ⊆ {0,1}*: there exists an algorithm A that decides L in polynomial time} 清华大学 宋斌恒 34 Polynomial time verifications • Verification algorithm A is a two arguments algorithm where one argument is an ordinary input string x and the other is a binary string y called a certificate. • A two arguments algorithm A verify an input x if there exists a certificate y such that A(x,y)=1. 清华大学 宋斌恒 35 Language defined by verification • L={x in {0,1}*: there exists y in {0,1}* such that A(x,y)=1} 清华大学 宋斌恒 36 NP的一个等价定义 • A language L belongs to NP if and only if there exists a two-input polynomial-time algorithm A and a constant c such that • L={x in {0,1}*: there exists y in {0,1}* with |y|=O(|x|c ) such that A(x,y)=1} • We say that algorithm A verifies language L in polynomial time