2000. május 24-én a Clay Mathematics Institute hét matematikai problémával állt elő, amelyek megoldása bármelyik problémára 1 000 000 USD jutalmat fog keresni a megoldó számára. Híresen ismert, mint a Millenniumi problémák, eddig, csak az egyik a hét probléma megoldódott eddig.

egymillió dollárt akar keresni, próbálja meg megoldani egyet ebből a listából. Ezek a problémák szerepelnek egy millió dolláros díjjutalomért.,

  1. Yang–Mills, valamint Tömeges Rés
  2. Riemann-Hipotézis
  3. P vs NP Probléma
  4. Navier–Stokes Egyenlet
  5. Hodge Találgatás
  6. Poincaré Sejtés
  7. Nyír Swinnerton-Dyer Találgatás

Oké, legyünk objektívek, ezek a problémák okkal van itt. Jól kitaláltad, ezeket a problémákat nehéz megoldani. Valójában ezek mély és nagyon nehéz, nem csak megoldani őket, de még megérteni a problémát nyilatkozatot. A felsorolt problémák nagy része alapos tárgyismeretre, elemzésre lesz szüksége, még a kérdés megértéséhez is.,

a Poincaré-sejtés az egyetlen probléma, amelyet e hét kérdés között megoldanak. Ez a probléma a topológia tartományból származik, amely azzal foglalkozik, hogy az objektumok hogyan illeszkednek egymáshoz és alakjuk az űrben. Ez a probléma kifejezetten a szférákhoz kapcsolódott.

1904-ben Henri Poincaré francia matematikus megkérdezte, hogy a háromdimenziós gömböt egyedülálló, egyszerűen összekapcsolt háromcsatornaként jellemzik-e. Ez a kérdés, a Poincaré-sejtés, Thurston geometriai feltevésének különleges esete volt., Perelman bizonyítéka azt mondja nekünk, hogy minden három sokrétű szabványos darabokból épül fel, mindegyik nyolc jól megértett geometriával rendelkezik.

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

bonyolult dolgok uhmmm! Lehetővé teszi, hogy megvitassák egy kicsit ezt, mielőtt a P versus NP.

Henri Poincaré 1904-ben jelentette ki a problémát, amely általánosságban azt állítja, hogy ha van egy lyuk nélküli objektum, amelynek mérete meglehetősen kicsi és véges, akkor gömb (vagy gömbré alakítható). Ez nem csak a 3 dimenzió, hanem minden dimenzió.,

de a kijelentést nem bizonyították a negyedik dimenzióra, amíg Grigorij Perelman 2003-ban nem találta meg a megoldást Richard Hamilton munkája alapján.

Ha érdekel, itt van, hogy néz ki egy millió dolláros megoldás:https://arxiv.org/abs/math/0211159

Grigorij Perelman egymillió dollárt és fields érmet kapott, mindkettőt elutasította.

mit mondjak? Néhányan közülünk szereti megoldani a problémákat,csak a móka kedvéért.

a boldogság élvezi a folyamatot!,

p versus NP a legutóbbi probléma, amely szerepel a Millenniumi problémalista. Ezt a problémát 1971-ben állapították meg.

A P versus NP probléma pontos megállapítását Stephen Cook 1971-ben mutatta be a “the complexity of theorem proving procedures”című szakácskönyvében.

A P versus NP probléma helyes megértése érdekében a számítási komplexitás alapvető ismerete elengedhetetlen. Valójában a P vs NP a számítástechnika leginkább várt problémája., Tehát egy jó tapadás arról, hogy ez a probléma hogyan befolyásolja a számítási tájat, segít nekünk megemészteni ezt a problémát.

Ha még nem ismeri a számítási komplexitás vagy általában a komplexitás témáját, nagyon bátorítom Önt, hogy vizsgálja meg az előző történetemet a ” mi a számítási komplexitás?”

a számítási tér legtöbb problémája döntési problémává csökkenthető. Ez olyan problémákat jelent, ahol a válasz IGEN vagy nem.

tehát térjünk vissza arra a kérdésre, hogy mi a p? és mi az az NP?,

mind a P, mind az NP olyan problémakészletnek tekinthető, amelyek csoportosítva vannak attól függően, hogy milyen nehéz megoldani és értékelni a megoldást. A nehéz kifejezés különösen fontos ebben az összefüggésben, ami alapvetően azt jelenti,hogy mennyire számításigényes a probléma megoldása és ellenőrzése.

például fontolja meg a szorzás problémáját. Ez viszonylag egyszerű probléma. Nem csak, hogy ezt a problémát könnyű megoldani, ez ugyanolyan könnyedén ellenőrizhető, csak a számok megszorzásával., Alapvetően minden olyan probléma, amely polinom időben megoldható, és amelynek eredménye polinom időben ellenőrizhető, a P.

p ( polinom idő) komplexitási halmaza alatt található, minden olyan döntési problémát tartalmaz, amelyet determinisztikus Turing gép segítségével lehet megoldani polinom számítási idő vagy polinom idő segítségével.

van ez a másik problémakészlet, amely polinom időben ellenőrizhető, de a probléma megoldása érdekében több mint polinom időt vesz igénybe. Vegyük például a Sudoku-t., Tekintettel arra, hogy bármilyen játékra van megoldás, könnyen ellenőrizhetjük. Ez azt jelenti, hogy meg tudjuk csinálni az ellenőrző részt polinom időben. De ahhoz, hogy megoldja a puzzle, több időre van szükségünk. A rácsok számának növekedésével a megoldás megtalálásának összetettsége exponenciálisan növekszik.

NP (nondeterminisztikus polinomidő) a döntési problémák osztályozására használt komplexitási osztály. Az NP azon döntési problémák halmaza, amelyekre a problémás esetek, ahol a válasz “igen”, polinom időben igazolhatók., (csak hagyjuk, hogy polinomosan nagy, nem nagyobb)

érdekes megjegyezni, hogy minden probléma, hogy a P is része NP. De ez lehet vagy nem lehet fordítva. Itt van, ahol a kutatási gondolkodásmód pitch-in. Tehát az NP problémák megoldása lassú, de gyorsan ellenőrizhető. Javíthatjuk-e a megoldás sebességét?

lehetővé teszi, hogy vizsgálja meg az elsődleges probléma. Az elsődleges teszt egy algoritmus annak meghatározására, hogy egy bemeneti szám prím-e.,

adott természetes szám n, n prím?

ezt a problémát az NP részhalmazban problémának tekintették, amíg az AKS primality teszt nem bizonyította, hogy ez a probléma p alatt van.,

AK primality teszt (úgy is ismert, mint Agrawal–Kayal–Saxena primality teszt, cyclotomic AKS teszt) egy determinisztikus primality-bizonyítva algoritmus létrehozott által közzétett Manindra Agrawal, Neeraj Kayal, valamint Nitin Saxena, számítógép tudósok az Indian Institute of Technology Kanpur, augusztus 6, 2002, egy cikk címe: “FŐVEZÉREK a P”

Szóval, van egy lehetőséget, hogy a probléma NP meg lehet oldani O komplexitás?, Vagy vannak olyan problémák, amelyek mindig nehéz megoldást találni arra, hogy a P és az NP mindig külön maradjon? A válasz ismeretlen. Valójában ez a millió dolláros probléma.

ha könnyű ellenőrizni, hogy a probléma megoldása helyes-e, akkor is könnyű megoldani a problémát?

jellemző az NP problémák, hogy a Hamiltoni út probléma: adott n városok, hogy látogassa meg, hogyan lehet ezt anélkül, hogy egy város kétszer? Ha megoldást adsz nekem, könnyen ellenőrizhetem, hogy helyes-e. De nem tudok olyan könnyen megoldást találni.,

Refer: https://www.claymath.org/millennium-problems / p-vs-np-problem

néhány probléma NP-ben NP-ként csoportosítható. Ez egy olyan problémacsoport, ahol ha a probléma bármelyikére gyors megoldást találunk, könnyedén megoldhatunk egy problémacsoportot ugyanabban a komplexitásban.

a probléma NP-teljes, ha meg lehet oldani egy korlátozott osztály nyers erő keresési algoritmusok, és lehet használni, hogy szimulálja bármely más probléma egy hasonló algoritmus.,

NP teljesség különösen fontos a P versus NP vita, mint a megoldás P időben, a probléma NP-teljes készlet bizonyítja, hogy a teljes komplexitás készlet összeomlik. Ami azt jelenti, hogy az NP-Complete = NP = p

egy NP-complete probléma NP-ben lesz, és NP-Hard lesz, ami azt jelenti, hogy ez a probléma legalább olyan nehéz, mint az NP bármely problémája, amint azt az alábbiakban mutatjuk be.,

a problem np-nehéz, ha egy megoldási algoritmus lefordítható egyre bármilyen NP-probléma (nem-determinisztikus polinom idő) megoldására. Az NP-hard tehát “legalább olyan kemény, mint bármely NP-probléma”, bár valójában nehezebb lehet.

vannak olyan problémák kívül NP, amelyek nehéz, hogy a megoldás ugyanakkor nehéz ellenőrizni a megoldást is, például, úgy sakk., Mivel bármilyen helyzetben a fórumon nehéz megtalálni a legjobb következő lépés is nehéz ellenőrizni a következő lépés, hogy pontos-e vagy sem. Ez a probléma EXP (exponenciális idő összetettsége), talán az NP-n kívül.

a számítási komplexitáselmélet területén a legtöbb kutató úgy véli, hogy a P nem egyenlő az NP-vel. Esemény bár sok érdekes probléma van az NP-ben, amely befolyásolja a mai életünket, mint az optimalizálási problémák. A megoldás egy NP teljes probléma, mint a fehérje összecsukható azt jelenti, hogy mi lesz sokkal közelebb kitalálni a gyógymód a rák., Továbbá, ha P = NP, akkor előfordulhat, hogy a nyilvános kulcsú kriptográfia megszakad, mivel ez az egész faktorizációtól függ, ami problémát jelent az NP-ben, és ettől a keménységtől függünk a legtöbb kriptográfia megoldásához. Tehát az n=NP bizonyításának következményei vegyesek.

sok kutatást végeztek a P = NP vagy fordítva bizonyítására. De ez a probléma maga úgy tűnik, hogy NP-kemény (csak szarkasztikus itt), mivel jelenleg nincs meggyőző eredmény. De a világ sokkal érdekesebb hely lesz, ha valaki bizonyítani tudja, hogy P=NP., De most, a legtöbb jól képzett ember a területen másképp gondolja.

blogjában, a híres kutató számítási komplexitáselméletében Scott Aaronson kijelenti, hogy

Ha P = NP, akkor a világ mélyen más hely lenne,mint általában feltételezzük. A “kreatív ugrásokban” nem lenne különösebb érték, nincs alapvető különbség a probléma megoldása és a megoldás felismerése között, ha megtalálják., Mindenki, aki értékelni tudja a szimfóniát, Mozart lenne; mindenki, aki lépésről lépésre követhet egy érvet, Gauss lenne; mindenki, aki felismeri a jó befektetési stratégiát, Warren Buffett lenne.

Köszönjük az idejét.

szerkesztette: Ashok Jeevan