NP两种定义是等价的 关于团问题属于NP的两种表述 用非确定性图灵机和验证算 类的 ·团:给定无向图和整数k,确定是否存在一个 定义是等价的 包含k顶点的完全子图【团】【 Clique】。 ·非确定图灵机算法:一个转移函数:给定k 可以不确定地转移到任意一个包含k个顶点的 图,然后确认该子图是否是团。其复杂度为 多项式 ·验证算法:给定一个k阶子图,验证它是否为 清华大学宋域恒 请华大学宋恒 CO-NP P is a subset of np of L in NPi P=NP=CO-NP NP=CO-NP 余集 P CO-NP NP 清华大学末斌恒 请华大学宋恒 The most possible cases NP-Complete and reducibility The"hardest"language in NP, with 多项式约简: we call Li is polynomial NP nCo-NP)NP- time reducible to L, denoted as L, s, L, if there exists a polynomial-time function f: 10, 1*210, 1)*such that for all x in 10, 1*, x in Li iff f(x)in Ly 清华大学末破恒 请华大学宋7 清华大学 宋斌恒 37 NP两种定义是等价的 • 用非确定性图灵机和验证算法给NP类的 定义是等价的 清华大学 宋斌恒 38 关于团问题属于NP的两种表述 • 团：给定无向图和整数k，确定是否存在一个 包含k顶点的完全子图【团】【Clique】。 • 非确定图灵机算法：一个转移函数：给定k， 可以不确定地转移到任意一个包含k个顶点的 子图，然后确认该子图是否是团。其复杂度为 多项式。 • 验证算法：给定一个k阶子图，验证它是否为 团。 清华大学 宋斌恒 39 co-NP • Complexity Class co-NP={L: complement of L in NP} • 余集 清华大学 宋斌恒 40 P is a subset of NP P=NP=co-NP NP=co-NP P Co-NP NP ∩co-NP NP =P 清华大学 宋斌恒 41 The most possible cases Co-NP NP ∩co-NP NP P 清华大学 宋斌恒 42 NP-Complete and reducibility • The “hardest” language in NP, with polynomial-time reducibility. • 多项式约简：we call L1 is polynomial￾time reducible to L2, denoted as L1 ≤p L2, if there exists a polynomial-time function f: {0,1}* Æ {0,1}* such that for all x in {0,1}*, x in L1 iff f(x) in L2