Op 24 mei 2000 kwam Clay Mathematics Institute met zeven wiskundige problemen, waarvoor de oplossing voor een van de problemen US $1.000.000 beloning voor de oplosser zal opleveren. Bekend als de Millenniumproblemen, tot nu toe is slechts één van de zeven problemen tot op heden opgelost.

wil je een miljoen dollar verdienen, probeer er een uit deze lijst op te lossen. Dit zijn de problemen genoemd voor een miljoen dollar prijs beloning.,

  1. Yang–Mills and Mass Gap
  2. Riemann-hypothese
  3. p vs NP-probleem
  4. Navier-Stokes-vergelijking
  5. vermoeden van Hodge
  6. vermoeden van Poincaré
  7. vermoeden van Birch en het vermoeden van Swinnerton-Dyer

Oké, laten we hier realistisch zijn, deze problemen zijn hier met een reden. Je raadt het goed, deze problemen zijn moeilijk op te lossen. In feite zijn ze diepgaand en echt moeilijk, niet alleen om ze op te lossen, maar zelfs om de probleemstelling te begrijpen. De meeste van de genoemde problemen zullen een gedegen kennis en analyse van het onderwerp nodig hebben, zelfs om de vraag te begrijpen.,het vermoeden van Poincaré is het enige probleem dat tussen deze zeven vragen is opgelost. Dit probleem komt uit het topologiedomein, dat zich bezighoudt met hoe objecten in elkaar passen en hun vorm in de ruimte. Dit probleem had specifiek betrekking op sferen.

In 1904 vroeg de Franse wiskundige Henri Poincaré of de driedimensionale sfeer gekarakteriseerd wordt als de unieke eenvoudig verbonden drie variëteit. Deze vraag, het vermoeden van Poincaré, was een speciaal geval van Thurstons vermeetkundigingsvermoeden., Perelman ‘ s bewijs vertelt ons dat elke drie variëteit is opgebouwd uit een set van standaard stukken, elk met een van de acht goed begrepen geometrieën.

Ref: https://www.claymath.org/millennium-problems

ingewikkeld spul uhmmm! Laten we hier wat meer van bespreken voordat we verder gaan naar P versus NP.

Henri Poincaré stelde het probleem in 1904, dat in het algemeen stelt dat, als je een object zonder gaten hebt en zijn grootte vrij klein en eindig is, het een sfeer is (of kan worden gemaakt tot een sfeer). Dit is niet alleen voor 3 dimensie, maar voor alle dimensies.,

maar de stelling werd niet bewezen voor de vierde dimensie, totdat Grigori Perelman in 2003 met de oplossing kwam, gebaseerd op werk van Richard Hamilton.

Als u geïnteresseerd bent, ziet u hier hoe een miljoen dollar oplossing eruit ziet: https://arxiv.org/abs/math/0211159

Grigori Perelman kreeg een miljoen dollar en fields medal, die hij beide weigerde.

wat te zeggen? Sommigen van ons vinden het leuk om problemen op te lossen, gewoon om het op te lossen.

geluk geniet van het proces!,

p versus NP is het meest recente probleem dat werd vermeld in de Millennium Problem list. Dit probleem werd in 1971 gesteld.de precieze verklaring van het P versus NP probleem werd in 1971 geïntroduceerd door Stephen Cook in zijn baanbrekende artikel “the complexity of theorem proving procedures”.

om het P versus NP probleem correct te begrijpen, is basiskennis van computationele complexiteit een must. In feite is P vs NP het meest verwachte probleem voor oplossing in de informatica., Een goede greep op hoe dit probleem het computerlandschap beïnvloedt, zal ons helpen dit probleem te verwerken.

als je nieuw bent op het onderwerp van computationele complexiteit of complexiteit in het algemeen, zal ik je sterk aanmoedigen om een kijkje te nemen in mijn vorige verhaal over ” wat is computationele complexiteit?”

De meeste problemen in de computationele ruimte kunnen worden teruggebracht tot een beslisprobleem. Dat betekent problemen waarbij het antwoord ja of nee is.

dus laten we teruggaan naar de vraag Wat is P? en wat is NP?,

zowel P als NP kunnen worden beschouwd als een reeks problemen die worden gegroepeerd op basis van hoe moeilijk het is om de oplossing op te lossen en te evalueren. De term moeilijk is vooral belangrijk in deze context, wat in feite betekent dat hoe rekenintensief een probleem is om de oplossing op te lossen en te controleren.

denk bijvoorbeeld aan het probleem van vermenigvuldiging. Dit is relatief eenvoudig op te lossen. Niet alleen dat dit probleem eenvoudig op te lossen is, dit kan ook met hetzelfde gemak worden geverifieerd door de getallen te vermenigvuldigen., In principe bevat elk probleem dat kan worden opgelost in polynoomtijd en waarvan het resultaat kan worden geverifieerd in polynoomtijd, onder de complexiteitsreeks van P.

P ( polynoomtijd) alle beslisproblemen die kunnen worden opgelost door een deterministische Turingmachine met behulp van een polynoom hoeveelheid rekentijd, of polynoomtijd.

Er is een andere reeks problemen die kunnen worden geverifieerd in polynoom tijd, maar, om dit probleem op te lossen zal het meer dan polynoom tijd. Laten we bijvoorbeeld Sudoku nemen., Gezien het feit dat we een oplossing hebben voor elk spel, kunnen we het gemakkelijk verifiëren. Dit betekent dat we het verificatiedeel in veeltermtijd kunnen doen. Maar om de puzzel op te lossen, hebben we meer tijd nodig. Ook als het aantal grids toeneemt, neemt de complexiteit van het vinden van een oplossing exponentieel toe.

NP (nonterministic polynomial time) is een complexiteitsklasse die wordt gebruikt om beslisproblemen te classificeren. NP is de verzameling beslisproblemen waarvoor de probleemgevallen, waar het antwoord “ja” is, bewijzen hebben die verifieerbaar zijn in polynomiale tijd., (alleen toegestaan om polynomiaal groot te zijn, niet groter)

interessant punt om op te merken is dat elk probleem in P ook een deel van NP is. Maar dit kan wel of niet andersom zijn. Hier is waar het onderzoek mindset pitch-in. Dus, oplossing voor NP problemen zijn traag, maar ze kunnen snel worden geverifieerd. Kunnen we de snelheid voor de oplossing verbeteren?

laten we het primaliteitsprobleem onderzoeken. Een primaliteitstest is een algoritme om te bepalen of een invoergetal een priemgetal is.,

gegeven natuurlijk getal n, is n priemgetal?

Dit probleem werd beschouwd als een probleem in NP-deelverzameling totdat de AKS-primaliteitstest aantoonde dat dit probleem onder P.,

De AKS primality-test (ook bekend als non commercial mf–Kayal–Saxena primality test en cyclotomic AKS test) is een deterministisch primality-bewijzen algoritme gemaakt en gepubliceerd door Manindra Agrawal, Neeraj Kayal, en Nitin Saxena, computer wetenschappers aan het Indian Institute of Technology Kanpur, op 6 augustus 2002, in een artikel met de titel “PRIEMGETALLEN is in P”

Dus, is er een mogelijkheid dat alle problemen in NP kan worden opgelost in P complexiteit?, Of zijn er problemen die altijd moeilijk te vinden zijn om P en NP altijd gescheiden te houden? Het antwoord is onbekend. In feite, dat is het miljoen dollar probleem.

als het gemakkelijk is om te controleren of een oplossing voor een probleem correct is, is het dan ook gemakkelijk om het probleem op te lossen?

kenmerkend voor de NP problemen is dat van het Hamiltoniaanse pad probleem: gegeven n steden om te bezoeken, Hoe kan men dit doen zonder een stad twee keer te bezoeken? Als u mij een oplossing geeft, kan ik gemakkelijk controleren of die juist is. Maar ik kan niet zo gemakkelijk een oplossing vinden.,

Ref: https://www.claymath.org/millennium-problems / p-vs-NP-probleem

sommige problemen in NP kunnen worden gegroepeerd als NP compleet. Dit is een groep van probleem waar als een snelle oplossing voor een van een van het probleem wordt gevonden kunnen we een groep van probleem op te lossen in dezelfde set van complexiteit met gemak.

een probleem is NP-compleet wanneer het kan worden opgelost door een beperkte klasse van brute force zoekalgoritmen en het kan worden gebruikt om elk ander probleem met een vergelijkbaar algoritme te simuleren.,

NP volledigheid is vooral belangrijk in P versus NP discussie als een oplossing in P tijd, voor een probleem in NP-complete set bewijst dat de gehele complexiteits set zal instorten. Dit betekent dat NP-Complete = NP = P

een NP-complete probleem in NP en in NP-Hard zal zijn, wat betekent dat dit probleem minstens zo moeilijk is als elk probleem in NP, zoals hieronder wordt geïllustreerd.,

een probleem is NP-moeilijk als een algoritme voor het oplossen van het kan worden vertaald in een voor het oplossen van een NP-probleem (niet-deterministische polynoom tijd) probleem. NP-hard betekent daarom “minstens zo hard als elk NP-probleem”, hoewel het in feite moeilijker zou kunnen zijn.

Er zijn problemen buiten NP die moeilijk zijn om een oplossing te maken en tegelijkertijd moeilijk zijn om de oplossing te controleren., Gezien elke positie op een bord is het moeilijk om de beste volgende zet te vinden ook is het moeilijk om te controleren of de volgende zet accuraat is of niet. Dit probleem ligt in EXP (exponentiële tijd complexiteit) en misschien buiten NP.

De meeste onderzoekers op het gebied van de computationele complexiteitstheorie geloven dat P niet gelijk is aan NP. Er zijn echter veel interessante problemen in NP die van invloed zijn op ons leven van vandaag, zoals optimalisatie problemen. Een oplossing voor een NP compleet probleem zoals eiwitvouwen betekent dat we veel dichter bij het vinden van de remedie voor kanker., Ook, als P=NP dan kunnen we vinden dat de public-key cryptografie te breken als het afhankelijk is van integer factorisatie wat een probleem is in NP en we zijn afhankelijk van deze hardheid voor de oplossing voor de meeste van onze cryptografie. Dus, implicaties van het bewijzen van N=NP is gemengd.

Er is veel onderzoek gedaan naar het aantonen van P = NP of vise-versa. Maar dit probleem zelf lijkt NP-hard (alleen sarcastisch hier) als er geen sluitende resultaten op dit moment. Maar de wereld zal veel interessanter zijn als iemand kan bewijzen dat P = NP., Maar vanaf nu denken de meeste goed opgeleide mensen van het veld er anders over.in zijn blog, famous researcher computational complexity theory, stelt Scott Aaronson dat,

Als P = NP, dan zou de wereld een heel andere plaats zijn dan we gewoonlijk aannemen. Er zou geen speciale waarde zijn in “creatieve sprongen”, geen fundamentele kloof tussen het oplossen van een probleem en het herkennen van de oplossing als het eenmaal is gevonden., Iedereen die een symfonie zou kunnen waarderen zou Mozart zijn; iedereen die een stap-voor-stap argument zou kunnen volgen zou Gauss zijn; iedereen die een goede investeringsstrategie zou kunnen herkennen zou Warren Buffett zijn.

Bedankt voor uw tijd.

bewerkt door Ashok Jeevan