isolation technique

《isolation technique》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IsolationTechniqueApril16,2001JasonKuTaoLiOutlineShowthatwecanreduceNP,withhighprobability,toUS.Thatis:NPrandomizedreducestodetectinguniquesolutions.PHPPPIsolationLemmaDefinitionsIsolationLemmaExampleofusingIsolationLemmaDefinitionofweightfunctionsAweightfunctionW,mapsafinitesetU+Foraset

2、SU,W(S)=xSW(x)LetFbeafamilyofnon-emptysubsetsofU.AweightfunctionWis“goodfor”FifthereisauniqueminimumweightsetinF,and“badfor”Fotherwise.Ex:letU={u1,u2,u3},letF={(u1),(u2),(u3),(u1u2)}defineW1(u1)=1W2(u1)=1W1(u2)=2W2(u2)=1W1(u3)=3W2(u3)=2W1isgoodforFwhileW2isbadforF.IsolationLemmaLetUbeafi

3、nitesetLetF1,F2,…Fmbefamiliesofnon-emptysubsetsofULetD=

4、

5、U

6、

7、LetR>mDLetZbeasetofweightfunctionss.t.theweightofanyindividualelementofUisatmostRLet,0<<1,bes.t.>mD/RThen,morethan(1-)

8、

9、Z

10、

11、weightfunctionsaregoodforallofF1,F2,…Fm.ProofofIsolationLemmaProofsketch:Bydefinition,aweightfunctionWis

12、badifthereareatleast2differentminimumweightsetsinF.LetS1andS2be2differentsetswiththesameminimumweights,thenxS1s.t.xS2.Callxambiguous.IfweknowtheweightsofallotherelementsinU,eitherxisunambiguous,orthereisonespecificweightforxthatmakesxambiguous.LetsCountSo,foranxU,thereareatmostRD-1weigh

13、tfunctionss.t.xisambiguous.ThereareRDweightfunctions,mchoicesforFandDchoicesforx.ThusthefractionofweightfunctionsthatarebadforFiisatmostmDRD-1/RD=mD/R<.SothefractionofweightfunctionsgoodforFiis1-.ExampleofIsolatingLemmaLetU={u1,u2,u3}D=3LetF1={(u1),(u1,u3),(u1,u2,u3),(u2)}m=1R=4>mD=3

14、

15、Z

16、

17、

18、=64Thenatleast(1–¾)64=16weightfunctionsaregoodforF.W1(u1)=1W2(u1)=2W3(u1)=1W4(u1)=1W1(u2)=2W2(u2)=3W3(u2)=2W4(u2)=3W1(u3)=3W2(u3)=4W3(u3)=2W4(u3)=36variations6variations3variations3variations18variations,andmore.DefinitionofUSUS={L

19、(NPTMM)(x)xL#accM(x)=1}NPrandomizedreducestoUSNPRPUSPr

20、oofMap:1)DefinitionsI,II2)ApplyIsolationLemmatogetaprobability3)ConstructanoracleBUS4)ConstructamachineNthatusesoracleB5)showNRPUS6)ShowxLNPimpliesxL(N)RPUSDefinitionsILetA={

21、NPTML(x)onpathyaccepts}forLNP,apolynomialp,s.t.x*,xLatleast1