Chapter 1The Self-Reducibility TechniqueMatt Boutell and Bill .ppt

上传人:arrownail386 文档编号:379635 上传时间:2018-10-09 格式:PPT 页数:14 大小:53.50KB
下载 相关 举报
Chapter 1The Self-Reducibility TechniqueMatt Boutell and Bill .ppt_第1页
第1页 / 共14页
Chapter 1The Self-Reducibility TechniqueMatt Boutell and Bill .ppt_第2页
第2页 / 共14页
Chapter 1The Self-Reducibility TechniqueMatt Boutell and Bill .ppt_第3页
第3页 / 共14页
Chapter 1The Self-Reducibility TechniqueMatt Boutell and Bill .ppt_第4页
第4页 / 共14页
Chapter 1The Self-Reducibility TechniqueMatt Boutell and Bill .ppt_第5页
第5页 / 共14页
亲,该文档总共14页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

1、Chapter 1 The Self-Reducibility Technique Matt Boutell and Bill Scherer CSC 486 April 4, 2001,Historical Perspective,Berman 1978: P=NP a tally set that is m-hard for NPMahaney 1982: P=NP a sparse set that is m-complete for NPOgiwara, Watanabe 1991: todays lecture,p,p,Theorem: If an NP btt-hard spars

2、e set S, then P = NP.Technique: let L be an arbitrary language in NP. Then, using S and the reduction, we give a deterministic polynomial algorithm to decide L.,Proof Overview,p,An Alternate Characterization of the Class NP,A language LNP AP, polynomial p | x*, xL IFF (w)wp(|x|) x,wA.x = input w = w

3、itness = certificate = accepting path: A = checking algorithm,Left Sets,The left set, denoted LeftA,p, is x,y | x* yp(|x|) (wp(|x|) w lex y x,wA.,Note that having the left set non-empty the existence of an accepting path.,Maximum Witnesses,The Maximum Witness for some input x, denoted wmax(x), is ma

4、xy | yp(|x|) x,yA.Deciding xL Determining if wmax(x) is defined.(x*)(yp(|x|)x,yLeftA,p ylex wmax(x). (1.4),LeftA,p NP,LeftA,p NP (by guessing wmax(x), so since S is NP-hard, LeftA,p btt S via some function f.,p,What does btt mean?,Bounded truth table reductions, btt, are a type of reduction that use

5、s a very weak form of oracle.Ak-ttB via some function f means that A = L(MB), where M is a deterministic polynomial machine that on input x precomputes up to k queries, asks them all in parallel, and uses a k-ary Boolean function to compute the output.v1 v2 v3 vk 0 0 0 0 Yes M: 0 0 0 1 No1 1 1 1 No,

6、p,p,p,Back to the Proof,Let u be a pair x,y. Then with our reduction, uLeftA,p S satisfies f(u).Now, with query strings v1, v2, v3, vk, let (S(v1), S(v2), S(v3), S(vk) Yes, No; this line is a row in the truth table in our reduction to S.So f(u) is of the form , v1, v2, v3, vk.,Intervals,The trick we

7、 will use is to generate a polynomially bounded list of candidates for wmax(x). Once this list is generated, we can use brute force computation to see if any of these candidates are in fact witnesses.We do this by keeping track of a set of pair-wise disjoint intervals in the range 0p(|X|)1p(|X|), st

8、arting initially with the entire range.,The Interval Invariant,xL wmax(x)UII (1.5),Last Definition: Covering,Let 1, 2 be two collections of pair-wise disjoint intervals over p(|x|). Then 1 covers 2 with respect to x if:1) (I2) (J1)IJ 2) wmax(x) UI1 wmax(x) UI2,0,2,1,Facts With Covering,Let 1, 2, 3,

9、4 be sets of pair-wise disjoint intervals over p(|x|). Then (all with respect to x):1) If the interval invariant holds for 1 and 2 is a cover of 1, it also holds for 2.2) If 2 covers 1 and 3 covers 2, then 3 covers 1.3) If 2 covers 1 and 4 covers 3, then 2U4 covers 1U3.,0,2,1,The Theorem, Restated,If an NP btt-hard sparse set S, then P = NP.,p,

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 教学课件 > 大学教育

copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
备案/许可证编号:苏ICP备17064731号-1