• 昔日港姐人到中年遇离婚,拍写真争取复出机会 2019-05-21
  • 猪的逻辑是没问题的,鉴定完毕 2019-05-07
  • 92岁大爷成网红:每天直播唱歌 2019-05-07
  • 守陵人强巴曲桑的故事 2019-05-04
  • 盘锦光合蟹业有限公司董事长李晓东获第十二届人民企业社会责任奖年度人物奖 2019-05-02
  • 端午三天8910万人次出游 世界杯点燃赴俄游热情 2019-05-02
  • 构建地区命运共同体的重要平台(望海楼) 2019-05-01
  • 新时代中国经济,如何转变发展方式 优化经济结构? 2019-04-28
  • 【寻找三秦非遗】【NO53】方寸之间雕刻乾坤万物,探访老艺人的核雕人生 2019-04-28
  • 神山冈仁波齐的转山之路文章中国国家地理网 2019-04-24
  • 好事要支持,解决劳动力更是好事 2019-04-24
  • 构建“选育管用带”培养链 磐安探索年轻干部培养“八法” 2019-04-21
  • [理上网来·辉煌十九大]孙来斌:把人民利益摆在至高无上的地位 2019-04-21
  • 呼死你团伙被摧毁 封停83万余个账号抓获210余人 2019-04-14
  • 计划不是产生在交换基础上的计划。 2019-04-12
  • 北京pk10是国家彩票吗
    下载

    0下载券

    加入VIP
    • 专属下载券
    • 上传内容扩展
    • 资料优先审核
    • 免费资料无限下载

    上传资料

    关闭

    关闭

    关闭

    封号提示

    内容

    北京pk10是国家彩票吗 《对类p是类np的真子集猜测的第二证明》论文

    北京赛车单双大小规律:《对类p是类np的真子集猜测的第二证明》论文.doc

    《对类p是类np的真子集猜测的第二证明》论文

    唐真zhen
    2018-11-14 0人阅读 举报 0 0 0 暂无简介

    北京pk10是国家彩票吗 www.qdpo.net 简介:本文档为《《对类p是类np的真子集猜测的第二证明》论文doc》,可适用于综合领域

    《对类p是类np的真子集猜测的第二证明》论文ASECONDPROOFOFTHECONJECTURETHATTHECLASSPISAPROPERSUBSETOFTHECLASSNPWANDONGXUAbstractTheproblemofdecidingwhetheranarbitraryundirectedplanargraphisaHamiltonian(HC)isoneofsixbestimportantNPcompleteprobGlemsIncurrentpaper,bythenecessaryandsufcientconditionofHC,oneturnedtheproblemHCintotheoneofdeterminingwhethertheredoesnothaveanyoneofforbiddensubgraphsineachofspanningsubgraphsofGItcanbecompletedinthepolynomialtimefordeterminingwhethertheredoesnothaveanyoneofforbiddensubgraphsinaspanningsubgraph,butitneverbecompletedinthepolynomialtimefordeterminingwhetherthereexistsatleastaspanningsubgraphinwhichthereneverhaveanyforbiddensubgraphininfinitemanyofspanningsubgraphsSuchthatonecandeducedthatthetimecomplexityofalgorithmforsolvingtheproblemHCis,(nn),herenistheorderofGandis>,thatis,itisextraexponentialofnSoonecanconcludethatHCPandP,NPKeywords:ProblemsofPversusNP,classP,classNP,Hamiltonian,Hamiltoniancycle,Hamiltoniangraph,computability,computationalcomplexityMSC:Q,Q,D,QXKDM:chthatthesolutiontothisproblemishugesignificancefortheproblemofNPcompletenessIfonecanshowbymeansofanalyzingtheproblemHC(notwithatheoreticaltransformationinpolynomialtimefromanotherNPcompleteproblem)thatitisunsolvableinpolynomialtimetodecidewhetheranarbitraryundirectedplanargraphisaHamiltonianornot,thenonecanconcludethatHC,PandP,NPanditwillbeshownthatistrueinthispaperAccordingtoanactualconditionofnecessaryandsufcienttotheproblemHC,whichpresentedbytheauthor,onecaneasydecidewitheyeswhetheraplanargraphisaHamiltonianornot,butacomputationalalgorithmcannotassuretosolvethisprobleminpolynomialtimesinceprobablyappearinginfinitemanyspanningsubgraphsoftheoriginalplanargraphinwhichthealgorithmshoulddeterminewhetherthereexistsatleastaspanningonethatinwhichthereneverhaveanyforbiddensubgraphtoaHamiltonianSuchthatonecanturntheproblemHCintotheoneofdeterminingwhethertherehasanyoneofforbiddensubgraphsineachofspanningsubgraphsItcanbecompletedinthepolynomialtimefordeterminingwhethertherehasanyoneofforbiddensubgraphsinaspanningsubgraph,butitneverbecompletedinthepolynomialtimefordeterminingwhetherthereexistsatleastaspanningsubgraphinwhichthereneverhaveanyforbiddensubgraphininfinitemanyofspanningsubgraphsInthispaper,onewill,inmosttraditionalandinessence,giveafullandparticularaccountofthisimportantpropositionmentionedaboveSometerminologies,symbolsandabbreviationsusedinthecurrentpaperisthesameasthatusedinrefThestepstodeterminewhetheranarbitraryundirectedplanargraphexcepttheoneofknight'stourisaHamiltonianItisverydifculttofindabestlargespanningsubgraphwhichisamaximal,planargraphfromanonplanargraphGsincetherearemanyspanningsubgraphs,ofGwhicharemaximalplanargraphsOnedoesnotknowitisintheclassPorintheclassNP,soonebeginshisdeterminationstartingfromanarbitraryundirectedplanargraphThedecidingwhetheranarbitraryundirectedplanargraphisaHamiltonian,ornot,isverycomplexTherearesomestepsforthisworkThoseareasfollows:(a)DeterminingwhetheranarbitraryundirectedgraphGisaconnectedgraphornot,namely,determining,(G)=or,(G)>,here,(G)isthenumberoftheconnectedcomponentinGIfthereis,(G)>,oneshoulddecidethegraphisn'ttheHamiltonian(b)IfGisasoleblockofplanargraph,oneshoulddeterminewhetherthereisavertexcutoredgecutinG,ornotIfthereis,oneshoulddetermineGissoleconnected,notconnected,thenoneshoulddecideGisn'taHamiltonianifthereisn'tanycutset,thengoon(c)DeterminewhetherallverticesareontheperipherycycleofGIfthoseare,thendecidetheGisatrivialHamiltonianandstoptheprocedureifthosearen't,thengoon(d)Determinewhetherthereexistsatleastacutofableedge,andorevenitisopenable,ontheperipherycycleofGAndifthereisnotso,thendecideGisanonHamiltonianifso,thencutitandgotonext(e)Electinorderalldistinctcombinationsofcutofableedgestocutthemof,respectively,anddeterminewhetherthereisaspanningsubgraphwhichstillisconnectedandinwhichthereacyclethrougheveryverticesexactlyonceinthosespanningsubgraphsofGIfthereis,thendecideGisaHamiltonianifthereisn't,thendecideGisanonHamiltonianThemaximalnumberoftheedgesallowedtobereallycutofforaHamiltonianAlthoughtherearemanycutofableedgesinagraphG,afewofthosemc,r()=m,nedgescanreallybecutofforaHamiltonianSincethenumberofedgesisequivalenttothatofverticesinaHamiltoniancycle,aftercutsomecutofableedgesthenumberofrestedgesneedstobethatofallverticesinG,otherwise,theremustnotexistanyHamiltoniancycleThereisagraphGsuchthattheorderisnandthesizeismAndoneletsmcbethenumberofcutofableedgesofwhichthedegreesoftwoendverticesare,,individually,andletsmbethemaximalnumberoftheedgesallowedtobec,rreallycutofHence,inaHamiltonianthereisAllofonesknowthataftercutacutofableedgeofinagraph,someothercutofableedgeswillturnintocutofunableedgesForinstance,thereisagraphGofFiga,wheren=andm=Thegraphoftheedgesallowedtobereallycutofm=,=Continually,letoneGhasm=,thecutofableedgese,e,euxande,butthemaximalnumberc,rcuwuvvxseekoutaHamiltoniancycleinGFirstly,ifonecutsanedgee(Figb),oranuvedge(Figc),thenotherthreerestedgesturnintocutofunableedgesinbotheuxfigures,andso,thereisn'tanyHamiltoniancycleNext,ifonecutsacutofableedgeisstille,theedgeseandeturnintocutofunableedgesbuttheedgeeuwuvuxvxGappearstobeacutofable,thenonecutsitofagain,andthegraphHamiltonianduotothereisaHamiltoniancycle(Figd)cnationsofthoseedgesinG,thereare,totallyandtheoretically,k=Meanwhile,onecanknowthataftercutsomecutofableedgesdistinctmmc,rPincombiis:kμmμμμspanningc,rXsubgraphsofXGSuchthatthetheoreticallytotalnumberofspanningsubgraphofG===mkckk=k=FigureThetranslationofcharacteristicofedgesfromacutofableedgesintoacutofunableonesaftercutsomeedgesinGInfact,whenonechoosesonesoutofcutofableedges,disregardingorder,tocutof,thoughtherearechoicespossible,onlyonecombinationcanreallybecut,owingtothatwhileonecutanedgeof,thenothercutofableedgesturnintothecutofunableedges,andnoothercombinationsofcutofableedgesexistHowever,onewillnotconsidersuchchangewhendeterminingwhetheraundirectedplanargraphisaHamiltonianornotbyacomputationalalgorithmNextexamplewillbeillustratedthisreasonm=m,n=Thenumberofallthepossiblewaystochoosekedgesoutc,rAregularundirectedplanargraphofcutofableedgesatatime,hereanddisregardingtheirHkofconnectedcircleoflayersinFigarunningovertomsuchthattheordern=andthesizem=Andtherearem=m=andc,rcorders,isμμμμμμX,o,,,,=max,k=kFigureAregulargraphconnectedwithcirclesoflayersFromFigb,onecanseethataftercutsomeedgesthespanningsubgraphofHisaHamiltoniancycleMeanwhile,onealsoknowthatinprocedureofcuttingitcannotberecognizedthathowmanyedgesturnintocutofunableedgesbyanalgorithm,orsay,theruntimeinwhichacomputerrecognizesallthecutofunableedgesthatoriginallyarecutofableislargerthantheruntimeofdeterminingwhetherthereisaHamiltoniancycleinthatspanningsubgraphSothatthoseedgeswillnotberecognizedbyacomputationalalgorithmHowtodecidewhetheranarbitraryundirectedplanargraphisaHamiltonianbyacomputationalalgorithmThereisanarbitrarysimpleplanargraphGexcepttheoneofknight'stour,finite,undirected,loopless,unweightedandlabeled,namely,agraphG=,V(n),E(m),,hereV(G)=,V,V,,=,(x,y),(x,y)v,,isthesetofvertices,itsorderisn,uvuandE(G)=,e,e,,isthesetofedges,itssizeism,wherethelettersu,uvuwvandw,u,=v,=w,arethelabelsofverticesandxandyarethecoordinatesofthoseverticesForaninputsofthecoordinatesxandyofnverticesandofmedges,ifthereisanedgebetweenVandV,then,,e,=,otherwise,euv,=,byacomputationaluvuvalgorithm,howtodecidewhetherthisgraphisaHamiltonianornotTherearemanystepswhichshouldbeinproceduresStep:DeterminewhethertherearesomecomponentsinGbyV(G)=,(x,y,(x,u)y),,andE(G)=,e,euw,,,ifGisasoleconnectedcomponentgraph,then,vuvdecide,(G)=andgoon,otherwise,decide,(G)>andGisanonHamiltonian,andstopprocedureStep:Foraconnectedgraphof,(G)=,determinewhethertherearesomecutverticesorcutedges,orsay,determinewhetherGisatleastaconnectedgraphornotIftherearesomeonesinG,thecomputershoulddecideGisasoleconnectedgraphanditisanonHamiltonian,andstopprocedureiftherearen'tanycutvertexorcutedgeinG,suchthatGisatleastconnected,thengoonStep:ThecomputerwouldnowrecognizewhichverticesareontheperipherycycleofG,abiggestoutsidecycleofhavingthebiggestareainG,anddeterminewhetherthereisatleastavertexinthiscycleornotIfthereis,thengoonifthereisn't,thendecideGisatrivialHamiltonianandstopprocedureStep:DeterminewhetherthereisatleastacutofableandopenableedgeontheperipherycycleofG,namelythereisacutofableedgeandnotreservedchainatitsbackIfthereis,thengotonextstepifthereisn't,thendecideGisanonHamiltonianandstopprocedureStep:Electallthecombinationsofmcutofableedgestakenkatactime,herekovertom,andcutthemof,individuallySuchthattheretotallyc,ryieldPmc,rmck=kspanningsubgraphsofGThen,determineinorderwhetherthenewlyappearedspanningsubgraphisonewhichstillisconnectedandinwhichthereneverappeartobeanyforbiddensubgraphtoaHamiltonian,ornotIfitisso,thendecideGisaHamiltonianifitisnotso,thendeterminenextspanningsubgraph,untilallthespanningsubgraphsaredetermined,anddecideGisanonHamiltonianHC,PandP,NPIntheabovesection,onecanseethattherearetotalofstepsintheprogramdetermining,andthelaststepsisthekeyfordecidingwhetheragraphisaHamiltonianornotExceptforthisstep,theotherofstepsareeasy,relatively,forrunningthosebyacomputerThecomplexityaboutruntimeforthesestepscanbelistedasfollowsThestepsistodeterminewhetheraplanargraphGispartitionedseveralcomponentsoronlyisagraphofalonecomponentSincethecomplexityofruntimefordeterminingtheconnectivityofaplanargraphisintheclassP,thecomplexityforrunningstepisanalogousasitThestepistodeterminethenumberofcutvertexandcutedgeinG,orsay,todeterminewhetherthisgraphisaconnectedgraphornotThereappearssomeresearchreportonthecomplexityofruntimeorrunspaceforthisdetermining,theresearchindicatedthatitcanbecompletedinpolynomialtimeSothatthisstepalsoisintheclassPThestepistodeterminewhatverticesandhowmanyverticesareontheperipherycycleofGTheproblemofdeterminingthecircumferenceofGisintheclassNPHowever,theproblemofdeterminingthegirthcycleofGcouldbesolvedinpolynomialtimeanditisintheclassPTheperipherycycleofGisanalogousasthelatter,hance,thetimecomplexitiesofdeterminingbothcyclesshouldbeidenticalsuchthatthisstepcouldbesolvedinpolynomialtime(Note:Otherpaperwillbetosolvethisproblem)ThestepistodeterminewhetherthereisatleastacutofableedgeanditevenisanopenableedgeontheperipherycycleofG,thisisequivalenttodeterminewhetherthedegreesoftwoendverticesofsomeedgewhichisontheperipherycycleare,ornotItshouldonlyrunoverallverticesexactlyoncewhichareontheperipherymcspanningsubgraphswhichareyieldedafterchoseanThestepistoobtainedgeoutofmcutofableedgesandcutitof,respectively,andtodetermineinordercwhetheroneofthosestillisconnectedornot,andwhetherinwhichthereisn'tanyforbiddensubgraphtoaHamiltonianIfso,thendecideGisaHamiltonianandstoptheprocedureifnotso,thengoon,Thestepistoobtainmspanningsubgraphs,herek=,,,m,,kcc,rwhichareyieldedafterchosekedgesoutofmcutofableedgesandcutthemof,crespectively,andtodetermineinorderwhetheroneofthosestillisconnectedornot,andwhetherinwhichthereisn'tanyforbiddensubgraphtoaHamiltonianIfmso,thendecidecGisaHamiltonianandstoptheprocedureifnotso,thengoon,,Thestepistoobtainspanningsubgraphswhichareyieldedafterchosemc,rmedgesoutofmcutofableedgesandcutthemof,respectively,andtodeterminec,rcinorderwhetheroneofthosestillisconnectedornot,andwhetherinwhichthereisn'tanyforbiddensubgraphtoaHamiltonianIfso,thendecideGisaHamiltonianandstoptheprocedureifnotso,thendecideGisanonHamiltonianandalsostoptheprocedure,,,Bythementionedabove,onecanknowsthatthesteps,andarekeysfordecidingprocessandthetimecomplexityofdecidingwhetheraarbitraryplanarisaHamiltonianwillbefocusonthesethreestepsNow,onehasTheoremcutofableedgesatatime,hereTheoremHC,PandP,NPanddisregardingtheirkrunningovertomc,rProof:ForanarbitraryundirectedplanargraphGsuchthattherearetheordernorders,isofGandthesizemLetmbethenumberofthecutofableedgesinm,andμμμμμcmc,rmccmcmletX,(),,,,maxmmc,rcmbethemaximumnumberoftheedgesallowedtobereallycutofforc,rkk=searchingSupposeaHamiltoniancycleinmcμμμμOneknowsthatthenumberofallthepossiblewaystochoosekedgesoutofccmcmmmμcm()max,,,,cmmc,rc,r=Henceμmc,rm!cX(),mcm!(m,m)!c,rcc,rkk=SuchthatthereareequivalentnumberofspanningsubgraphsthatareshouldbedeterminedwhetherthereisatleastahamiltoniancycleinthoseThetimecomplexityfordeterminingwhetherasubgraphisstillconnectedandwhetherthereexistsaforbiddensubgraphtotheHamiltonianinaspanningsubgraphbyacomputationalalgorithmisinpolynomialtime,namelyis,(n)Andso,forsuchmanyofspanningsubgraphsofGthetimecomplexityofadeterminingalgorithmism!nc())f(n)=,(g(n))=,(m!(m,m)!c,rcc,rSincetherearefourcasesfortherelationshipbetweentheordernofGandthenumbermofcutofableedgesinG,thatis,()m<n,()n,m<n,()cccm=nand()m>n,oneshouldanalyzethosecases,respectively,asfollowscc()Whenm<ninG,generally,therehascnmn,g(n)=<!m!(m,m)!cc,rcc,robtainedbyanapproximatingestimation,notdeducedAndthisresultneverbeacceptedforsettingforthitstimecomplexity()Whenn,m<n,itispossiblethattherehascm!ncn,g(n)=,m!(m,m)!c,rcc,robtainedalsobyanapproximatingestimationAndthisresultneveralsobeaccepted,theoretically()Whenm=n,oneassumesthatm=m,andtherehasccm!n(n)!nc=g(n)=(n!)m!(m,m)!c,rcc,rnn,(n,),(n,),,,(n)=n!n,nnn,?(n,),,,(),=nn,n!nnnn,,n,,n,,,,=n),(,),,,(nnnn,,,,n,,nn=n,n,,n(),(,),,,n()Whenm>n,onealsoassumesthatm=m,andtherehasccmnm!n(c,=g(n)=)!mc,r!n!cm!(m,m)!c,rcc,rowingtom>nandm=m,n>n,thereare(m)!>(n)!andm!>n!,onecc,rcc,rcannowdecidethattheformerisfastincreasingthanthelatterwhennissufcientlarge,andthereisn(n)!g(n)>,(n!)henceg(n)onnSothatonecanconcludeng(n)=n,here>Inthiscase,thetimecomplexityisn()f(n)=,(n,)here>,namelyintheworstcaseitisextraexponentialofnUptonow,onecanconcludethatHC,PandP,NPSeveralexamplesExample:AundirectedplanargraphGofFigasuchthattheordern=andthesizem=Andtherearem=andm=inGThen,aftercutcc,rsomecutofableedgesofthenumberofallthespanningsubgraphsisμμμXn<<==,,,kk=FigureAnarbitraryplanargraphwhichisaHamiltonianTheretotallyareofspanningsubgraphsofG,however,thereareonlyofonesinthemwhichhaveaHamiltoniancycle(FigbandFigc)Intheworstcase,acomputershouldruntimesofdeterminingworksandthenmaydecideGisaHamiltonianExample:AundirectedplanargraphGofFigasuchthattheordern=andthesizem=Andtherearem=andm=inGThen,aftercutμμμcc,rXnsome<<==,,,kcutofableedgesofthenumberofallthespanningsubgraphsisk=TheretotallyareofspanningsubgraphsofG,however,noneofthemhasaHamiltoniancycle(Figb)SuchthatacomputermustruntimesofdeterminingworksandthenmaydecideGisanonHamiltonianExample:AundirectedplanargraphAofFigasuchthattheordern=andthesizem=Andtherearem=andmAThen,aftercutincc,rsome=FigureAplanargraphinwhichtherewillappeartobeanadjointsubgraphofcentralvertexuofd(u)=aftercutsomecutofableedgescutofableedgesofthenumberofallthespanningsubgraphsisμμXμμn=,>,,,,,kk=FigureAnarbitraryplanargraphAinwhichalltheedgesarecutofableTheretotallyaremorethanofspanningsubgraphsofA,however,thereareonlyfewofthosewhichhaveaHamiltoniancycle(FigbandFigc)Intheworstcase,acomputershouldrunmorethantimesofdeterminingworksandthenmaydecideAisaHamiltonianExampleandExample:TheTuttegraphTofFigandtheGringberggraphGofFigsuchthatboththeordern=andthesizem=Andthereallarem=m=andm=,=inTandinGThen,aftercutsomecc,rcutofableedgesofinTandinGthenumberofthespanningsubgraphsofbothgraphsallisμμμμnX=,,,,,=kk=FigureTheTuttegraphinwhichtheredoesnotexisttheHamiltoniancycleFigureTheGringberggraphGinwhichtheredoesnotexisttheHamiltoniancycleTheretotallyaremorethanofspanningsubgraphsofTandG,noneofthosehasaHamiltoniancycle(FigandFig)Andso,acomputermustrunmorethantimesofdeterminingworksandthenmaydecidebothgraphsarethenonHamiltonianTherearesomepossiblecasesastypicalissuesoffactThereisaHamiltoniansubwaybetweenuandvviaobutthereisn'tsuchasubwaybetweenthemviaxandy,orsay,thereisadoublebridgeswithdoublechainscandcinFigaanduxvuyvthereisasubwaybetweenpandqviaobutthereisn'tsuchasubwaybetweenthemviatandsandr,orsay,thereisahomeomorphicdoublebridgeswithdoublechainscandcinFigbptqpsrqThereisaHamiltoniansubwaybetweenlandqviaobutthereisn'tsuchasubwaybetweenthem,orsay,thereisahomeomorphicdoublebridgeswithdoublechainscandcinFigaandthereisasubwaybetweenuandvviaobutthereisn'twouldbecutdoublebridgeswithdoublechainscandcifanedgeelmqlnpquzvuwqpxyvwyof,suchasubwaybetweenthemviamandnandp,orsay,thereisahomeomorphicorthereappearstobeasoleconnectedspanningsubgraphifanedgewouldbeeuwcutof,inFigbExample:AundirectedplanargraphMofFigwhichisaregularplanarconnectedwithcirclesoflayerssuchthattheordern=andthesizem=Andtherearem=andm=inMThen,aftercutsomecutofablecc,redgesofthenumberofallthespanningsubgraphsisFigureAregulargraphconnectedwithcirclesoflayersμμX!μμ=k=,,,,k=(!),,,,=!?,,,,,=!?,,,,=!,n=,,,TheretotallyaremorethanofspanningsubgraphsofM,however,thereareonlyfewofthosewhichhaveaHamiltoniancycle(Fig)OnebelievesthatthisweretheundergroundpalaceofMonsterMinotaur's,hehadhiddeninasmallsecretroomtinM,andPrinceTheseushappenedtoenterintotheroomtstartingatsandalonganopenedcorridor,thenkilledMinotaurHowever,acomputer,intheworstcase,shouldrunmorethantimesofdeterminingworksandyetfindaHamiltoniancycleinM,finally,decidesMisaHamiltonianhadbeendeleted,,Example:AgraphMofFigainwhichanoriginaledgeeuvcomparedwiththegraphMofFig,andaddedofverticesx,andybetweenuandv,andaddedofedgese,e,exv,andeyvNowthereisagraphoftheuxuyorder,n=andthesizem=suchthatm=andm=inMSincetherecc,rappearsanewlyforbiddensubgraphofadoublebridgeswithdoublechains,candc,atthetime,noHamiltoniancycleisinthisgraph,andMisanonHamiltonianuxvuyvFigureAchangedgraphofregulargraphconnectedwithcirclesoflayers,IfonecutssomecutofableedgesofinM,thenthetotalnumberofallthespanningsubgraphsisμμXμμ=,!k=,,,,,k=(!)(!),,,,,=!?,,,,,,,,=!?,,,,,=!n?,,,,,TheretotallyaremorethanofspanningsubgraphsofM,noneofthosehasaHamiltoniancycleThereisatypicaloneinthose,inwhichthereisaHamiltoniansubwaybetweenuandvviaw,butthereisn'tsuchasubwaybetweenthemviaxandandcy,thereisaforbiddensubgraphofdoublebridgeswithdoublechainscuyvuxv(Figb)Andso,acomputermustrunmorethantimesofdeterminingworks,andthenmaydecideMisanonHamiltonianSothatitcanneverbefinishedinpolynomialtimeRemarkTheexponentialontimecomplexityisworse,however,ityetissuperiorityfromthefactorialGenerally,theproblemofHCissolvedbythebacktrackingmethod,thatisthefactorialofnodenumberontimecomplexityOntheonehand,whentheordernandsizemandthenumberofcutofableedgesminaplanargraphcaren'tsufcientlarge,thealgorithmpresentedincurrentpaperisefectivelyForexample,agraphGofFigsuchthattheordern=andsizem=,andthenumberofcutofableedgesm=andthemaximalnumberofedgesallowedtocbereallycutofm=,hencethetheoreticallytotalnumberofspanningsubgraphsc,rofGisAndtheruntimefordeterminingwhetherGisaHamiltonianornotis,,t=,n=,butbythebacktracking,thereisT=n!=nodesinthestatespace,sotheformerislargelysuperiorthanthelatterOntheotherhand,whenn,mandminagrapharesufcientlarge,thealgorithmcpresentedincurrentpaperisnotefectivelybutstillissuperiorfromthebacktracking,Forexample,agraphMofFigsuchthatn=,m=andm=,cthus,theruntime,forthealgorithmpresentedincurrentpaper,ist=,!!,!,,However,theruntime,forthealgorithmofthebacktracking,is,T=!=,Theformerstillissuperiorthanthelatteralthoughbotharen'tinpolynomialtimeReferencesAMTuring,Oncomputablenumber,withanapplicationtotheentscheidungproblem,ProcLondonMathSoc,(),ppAGDebus,WorldWho'sWhoinSciencefromAntiquitytothePresent,MarquisWho'sWhoIncorporated,Chicago,JEdmonds,Path,trees,andowers,CanadJMath()ppSJCook,Thecomplexityoftheoremprovingprocedures,ProcrdAnnACMSymponTheoryofComputing,AssociationforComputingMachinery,NewYork,pp()RMKarp,Reducibilityamongcombinatorialproblems,InComplexityofComputerComputations,edbyREMillerandJWThatcher,PlenumPress,pp()SJCook,TheproblemsofPversusNP,CHPapadimitriou,ComputationalComplexity,AddisonWesley,pp()MRGareyandDSJohnson,ComputersandIntractabilityAGuidetotheTheoryofNPCompleteness,BellTelephoneLaboratoriesIncorporated,()AWigderson,Thecomplexityofgraphconnectivity,edDeCaiLi,LectureNoteSeriesonComputing,,pp()DBWest,IntroductiontoGraphTheory,SecondEdition,PearsonEducationAsiaLtd,pp,pp,()WDXu,Howtodecidewhetheraplanargraphisregularlycolorable,Firstcorrectededition,WDXu,AproofoftheconjecturethattheclassPisapropersubsetoftheclassNP,WDXu,Howtodecidewhetheranarbitraryundirectedgraphexceptthegraphoftheknight'stourisaHamiltonian,MHAlsuwaiyel,AlgorithmsDesignTechniquesandAnalysis,WorldScientificPublishingCoPteLtd,Singapore,pp(

    用户评价(0)

    关闭

    新课改视野下建构高中语文教学实验成果报告(32KB)

    抱歉,积分不足下载失败,请稍后再试!

    提示

    试读已结束,如需要继续阅读或者下载,敬请购买!

    评分:

    /41

    VIP

    在线
    客服

    北京pk10是国家彩票吗

    爱问共享资料服务号

    扫描关注领取更多福利

  • 昔日港姐人到中年遇离婚,拍写真争取复出机会 2019-05-21
  • 猪的逻辑是没问题的,鉴定完毕 2019-05-07
  • 92岁大爷成网红:每天直播唱歌 2019-05-07
  • 守陵人强巴曲桑的故事 2019-05-04
  • 盘锦光合蟹业有限公司董事长李晓东获第十二届人民企业社会责任奖年度人物奖 2019-05-02
  • 端午三天8910万人次出游 世界杯点燃赴俄游热情 2019-05-02
  • 构建地区命运共同体的重要平台(望海楼) 2019-05-01
  • 新时代中国经济,如何转变发展方式 优化经济结构? 2019-04-28
  • 【寻找三秦非遗】【NO53】方寸之间雕刻乾坤万物,探访老艺人的核雕人生 2019-04-28
  • 神山冈仁波齐的转山之路文章中国国家地理网 2019-04-24
  • 好事要支持,解决劳动力更是好事 2019-04-24
  • 构建“选育管用带”培养链 磐安探索年轻干部培养“八法” 2019-04-21
  • [理上网来·辉煌十九大]孙来斌:把人民利益摆在至高无上的地位 2019-04-21
  • 呼死你团伙被摧毁 封停83万余个账号抓获210余人 2019-04-14
  • 计划不是产生在交换基础上的计划。 2019-04-12
  • 腾讯分分彩怎么倍投 浙江体彩6+1开奖结果 福彩幸运赛车对单 怎样买刮刮乐中大奖 腾讯彩票专家预测 千禧3d试机号10期金码 澳洲幸运8是什么彩票 捕鱼游戏单机版 六合彩走势图 时时彩论坛 决胜21一点剧情解析 重庆时时彩开奖结果表 体彩p5直播开奖结果查询 极速时时彩能玩吗 足球队 七乐彩走势图带连线