資源描述：
《The history and status of P verse NP question》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
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
