资源描述：
《The history and status of P verse NP question》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、TheHistoryandStatusofthePversusNPQuestionMichaelSipser*DepartmentofMathematicsMassachusettsInstituteofTechnologyCambridgeMA02139Aslongasabranchofscienceoffersanabundanceofproblems,solongitisalive;alackofproblemsforeshadowsextinctionorthecessationofindependentdevelopment.—DAV
2、IDHILBERT,ilomalecturedeliveredbeforetheInternationalCongressofMathematiciansatParisin1900.When?—JURISHARTMANIS1Significancesomewhereinalargespaceofpossibilities.Comput-ersmaygreatlyspeedupthesearch,buttheextremelyThePversusNPquestiongrewoutofdevelopmentsinlargespacesthatrea
3、llydooccurincasesofinterestmathematicallogicandelectronictechnologyduringthewouldstillrequiregeologictimetosearchexhaustivelymiddlepartofthetwentiethcentury.Itisnowconsid-evenonthefastestmachinesimaginable.Theonlywayeredtobeoneofthemostimportantproblemsincon-tosolvesuchcases
4、practicallywouldbetofindamethodtemporarymathematicsandtheoreticalcomputersci-whichavoidedsearchingbybruteforce.Roughlyspeak-ence.Theliteratureonthissubjectisdiversebutnoting,thePversusNPquestionaskswhether,ingeneral,huge—itispossibleforthestudenttoacquainthimselfsuchamethode
5、xists.withalloftheimportantrelevantworkinasemesterorThisquestionhasattractedconsiderableattention.two.Inwritingthwarticle,Ihaveattemptedtoorga-Itsintuitivestatementissimpleandaccessibletonon-nizeanddescribethisLiterature,includinganoccssiom-dspecialists,eventhoseoutsideofsci
6、ence.Byembracingopinionaboutthemostfruitfuldirections,butnotech-issuesinthefoundationsofmathematicsaswellasinthenicaldetails.practiceofcomputing,itgainssomethingincharacterInthefirsthalfofthiscentury,workonthepowerofbeyondthatofamerepuzzle,butratherwithappar-formalsystemsled
7、totheformalizationofthenotionofentlydeepersignificanceandbroaderconsequences.algorithmandtherealizationthatcertainproblemsareChurchandTuring,intheirworkonHilbert’salgorithmicallyunsolvable.Ataroundthistime,fore-entschiedungsproblem,haveshownthattestingwhetherrunnersoftheprog
8、rammablecomputingmachinewereanassertionhasaproofisidgorithmicallyunsolvable
