Na 24. Května 2000 Clay Mathematics Institute přišel se sedmi matematických problémů, na které řešení pro jakýkoliv problém NÁM bude vydělávat $1,000,000 odměnu pro řešitele. Známý jako problémy tisíciletí, zatím je vyřešen pouze jeden ze sedmi problémů.

Chcete vydělat milion dolarů, zkuste vyřešit jeden z tohoto seznamu. To jsou problémy uvedené za odměnu milion dolarů.,

  1. Yang–Mills a Hmotnost Mezera
  2. Riemann Hypotéza
  3. P vs. NP Problém
  4. Navier–Stokes Rovnice.
  5. Hodge Conjecture
  6. Poincaré Domněnkou
  7. Břízy a Swinnerton-Dyer Dohad

Dobře, buďme realisté, tyto problémy jsou tady z nějakého důvodu. Uhodli jste to správně, tyto problémy je těžké vyřešit. Ve skutečnosti jsou hluboké a opravdu obtížné, nejen je vyřešit, ale dokonce pochopit problémové prohlášení. Většina z uvedených problémů bude potřebovat zvukové znalosti a analýzu předmětu, a to i pro pochopení otázky.,

Poincaré Conjecture je jediný problém, který je vyřešen mezi těmito sedmi otázkami. Tento problém je z topologie domény, která se zabývá tím, jak objekty zapadají do sebe a jejich tvar v prostoru. Tento problém se konkrétně týkal sfér.

V roce 1904 francouzský matematik Henri Poincaré se zeptal, zda tří-dimenzionální koule je charakterizován jako unikátní jednoduše připojí tři potrubí. Tato otázka, domněnka Poincaré, byla zvláštním případem thurstonovy geometrizační domněnky., Perelman důkaz nám říká, že každé tři potrubí je postaven ze sady standardních kusů, každý s jedním z osmi dobře pochopil geometrií.

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

Komplikované věci uhmmm! Pojďme diskutovat o něco více z toho před přechodem na P versus NP.

Henri Poincaré, uvedl, že je problém v roce 1904, která ve velmi obecné států, které, pokud máte objekt s žádné otvory a její velikost je poměrně malá a omezená, pak je koule (nebo může být do sféry). To není jen pro Rozměr 3, ale pro všechny rozměry.,

ale prohlášení nebylo prokázáno pro čtvrtou dimenzi, dokud Grigori Perelman nepřišel s řešením v roce 2003 na základě práce Richarda Hamiltona.

Máte-li zájem, zde je to, co milion dolarů řešení vypadá: https://arxiv.org/abs/math/0211159

Grigori Perelman získal jeden milion dolarů a fields medaili, z nichž oba odmítl.

co říct? Někteří z nás rádi řeší problémy, jen pro zábavu při řešení.

štěstí se těší procesu!,

p versus NP je nejnovější problém, který byl uveden v seznamu problémů tisíciletí. Tento problém byl uveden v roce 1971.

přesné prohlášení na P versus NP problém byl zaveden v roce 1971 Stephen Cook ve své podnětné knize „složitost dokazování teorémů postupy“.

aby bylo možné správně porozumět problému P versus NP, základní znalost výpočetní složitosti je nutností. Ve skutečnosti P vs NP je nejočekávanější problém pro řešení v informatice., Takže dobrá přilnavost toho, jak tento problém ovlivňuje výpočetní krajinu, nám pomůže tento problém strávit.

Pokud jste novým tématem výpočetní složitosti nebo složitosti obecně, velmi Vás povzbudím, abyste se podívali na můj předchozí příběh o “ co je výpočetní složitost?“

většina problémů ve výpočetním prostoru může být redukována na problém s rozhodnutím. To znamená problémy, kde je odpověď buď ano, nebo ne.

takže se můžete vrátit k otázce, Co je P? a co je NP?,

P i NP lze považovat za soubor problémů, které jsou seskupeny na základě toho, jak obtížné je řešení vyřešit a vyhodnotit. Termín obtížný je v této souvislosti obzvláště důležitý, což v podstatě znamená, že jak výpočetně náročný je problém vyřešit a zkontrolovat řešení.

například zvažte problém násobení. To je relativně snadný problém vyřešit. Nejen, že tento problém lze snadno vyřešit, lze jej také snadno ověřit vynásobením čísel., V podstatě, jakýkoli problém, který může být vyřešen v polynomiálním čase, a výsledek, který lze ověřit v polynomiálním čase, je pod složitost sada P.

P ( polynomial time) obsahuje všechny rozhodovací problémy, které mohou být řešeny pomocí deterministického Turingova stroje pomocí polynomiální množství výpočetního času, nebo polynomiálním čase.

existuje další sada problémů, které lze ověřit v polynomiálním čase,ale pro vyřešení tohoto problému to bude trvat déle než polynomiální čas. Vezměme si například Sudoku., Vzhledem k tomu, že máme řešení pro jakoukoli hru, můžeme ji snadno ověřit. To znamená, že můžeme provést ověřovací část v polynomiálním čase. Ale abychom vyřešili hádanku, potřebujeme více času. Také jak se počet sítí zvyšuje, složitost nalezení řešení se exponenciálně zvyšuje.

NP (nedeterministické polynomiální čas) je složitost třídy používá pro klasifikaci rozhodovací problémy. NP je soubor rozhodovacích problémů, pro které mají problémové případy, kde je odpověď „Ano“, důkazy ověřitelné v polynomiálním čase., (prostě dovoleno být polynomially velký, ne větší),

Zajímavý bod k poznámce je, že každý problém, který je v P je také součástí NP. Ale to může nebo nemusí být vise-versa. Zde je místo, kde výzkum myšlení pitch-in. Řešení problémů s NP je tedy pomalé, ale lze je rychle ověřit. Můžeme zlepšit rychlost řešení?

umožňuje podívat se do problému primality. Test primality je algoritmus pro určení, zda je vstupní číslo prvočíslo.,

dané přirozené číslo n, je n prime?

Tento problém byl považován za problém v NP podmnožinu do AKS primality test prokázal, že tento problém je pod P.,

AKS primality test (také známý jako Agrawal–Kayal–Saxena primality test a cyclotomic AKS test) je deterministický prvočíselnosti-dokázat algoritmus vytvořil a publikoval Manindra Agrawal, Neeraj Kayal a Nitin Saxena, počítačových vědců na Indian Institute of Technology, Kanpur, 6. srpna 2002, v článku s názvem „PRVOČÍSEL je v P“

Takže, je tu možnost, že všechny problémy v NP může být vyřešen v P složitosti?, Nebo existuje řada problémů, které bude vždy těžké najít řešení, aby P a NP vždy zůstaly oddělené? Odpověď není známa. Ve skutečnosti je to problém milionů dolarů.

pokud je snadné zkontrolovat, zda je řešení problému správné, je také snadné problém vyřešit?

typické pro problémy NP je problém Hamiltonovské cesty: vzhledem k tomu, že n města k návštěvě, jak to lze udělat bez návštěvy města dvakrát? Pokud mi dáte řešení, mohu snadno zkontrolovat, zda je správné. Ale nemohu tak snadno najít řešení.,

viz: https://www.claymath.org/millennium-problems / p-vs-NP-problem

některé problémy v NP mohou být seskupeny jako NP kompletní. Jedná se o skupinu problémů, kde je-li nalezeno rychlé řešení kteréhokoli z nich, můžeme snadno vyřešit skupinu problémů ve stejné sadě složitosti.

problém je NP-kompletní, když může být vyřešen omezenou třídou algoritmů vyhledávání hrubou silou a může být použit k simulaci jakéhokoli jiného problému s podobným algoritmem.,

NP úplnost je důležité zejména v P versus NP diskusi jako řešení v P čas, pro problém v NP-kompletní sada dokazuje, že celá složitost nastavení se zhroutí. Což znamená, že NP-Complete = NP = p

problém NP-complete bude v NP a bude v NP-Hard, což znamená, že tento problém je přinejmenším stejně těžký jako jakýkoli problém v NP, jak je znázorněno níže.,

problém je NP-těžké, pokud algoritmus pro řešení může být přeložen do jednoho pro řešení NP-problém (nedeterministické polynomiální čas) problém. NP-hard tedy znamená „alespoň tak tvrdý jako jakýkoli NP-problém“, i když to může být ve skutečnosti těžší.

existují problémy mimo NP, které je obtížné provést řešení současně obtížné zkontrolovat řešení, například zvážit šachy., Vzhledem k jakékoli pozici na desce je těžké najít nejlepší další krok také je těžké ověřit další krok, aby byl přesný nebo ne. Tento problém je v EXP (exponenciální časová složitost) a možná i mimo NP.

většina vědců v oblasti teorie výpočetní složitosti se domnívá, že P se nerovná NP. Událost ačkoli existuje mnoho zajímavých problémů v NP, které ovlivňují náš dnešní život jako optimalizační problémy. Řešení úplného problému NP, jako je skládání bílkovin, znamená, že budeme mnohem blíže k nalezení léku na rakovinu., Také, pokud P=NP, pak můžeme najít public key cryptography, aby se porušovala, neboť závisí na celé číslo faktorizace, což je problém v NP a jsme závislí na této tvrdosti pro řešení pro většinu našich kryptografie. Takže důsledky prokázání n=NP jsou smíšené.

bylo provedeno mnoho výzkumů, které prokázaly buď P = NP, nebo naopak. Ale tento problém sám o sobě se zdá být NP-hard (jen sarkastický zde), protože zatím neexistují žádné přesvědčivé výsledky. Ale svět bude mnohem zajímavější místo, pokud někdo dokáže, že P=NP., Většina vzdělaných lidí z oboru si ale zatím myslí opak.

Ve svém blogu, slavný výzkumník výpočetní složitosti teorie, Scott Aaronson státy,

Pokud P = NP, pak se svět by byl velmi odlišné místo, než jsme obvykle předpokládat, že je. V „kreativních skocích“ by neexistovala žádná zvláštní hodnota, žádná zásadní mezera mezi řešením problému a rozpoznáním řešení, jakmile bude nalezeno., Každý, kdo by mohl ocenit symfonii, by byl Mozart; každý, kdo by mohl následovat krok za krokem, by byl Gauss; každý, kdo by poznal dobrou investiční strategii, by byl Warren Buffett.

Díky za váš čas.

editoval Ashok Jeevan