P=NP

Wikipedia
Loikkaa: valikkoon, hakuun
Vaativuusluokat NP, P ja NP-täydellinen.

P = NP? on laskennan vaativuusteorian kuuluisimpia ratkaisemattomia ongelmia. Ongelmassa yritetään ratkaista vaativuusluokkien P ja NP suhdetta. P = NP? -ongelma voidaan ilmaista "Jos jonkin ongelman ratkaisu voidaan tarkastaa tehokkaasti, niin voidaanko ongelma myös ratkaista tehokkaasti?".

Luokkaan P (polynomial) kuuluvat kaikki ongelmat, jotka tiedetään voitavan ratkaista "tehokkaasti" eli polynomisessa ajassa. Luokkaan NP (non-deterministic polynomial) taas kuuluvat ongelmat, joiden ratkaisun oikeellisuus voidaan tarkastaa tehokkaasti. Määritelmän perusteella P ⊆ NP.

NP-täydelliseksi kutsutaan sellaista luokan NP-ongelmaa, jolle polynomisessa ajassa toimivan ratkaisun löytyminen merkitsisi sitä, että kaikkiin luokan NP-ongelmiin löytyisi polynomisessa ajassa toimiva ratkaisu. NP-täydellisiin ongelmiin kuuluu mm. kauppamatkustajan ongelma ja lukuisia muita tärkeitä ongelmia. Nykyisin kaikki tunnetut NP-täydellisten ongelmien ratkaisualgoritmit ovat ylipolynomisia, eli niiden vaativuus kasvaa erittäin nopeasti ongelman suuruusluokan kasvaessa.

Vaativuusteorian kuuluisimpia ongelmia on näiden kahden luokan välinen suhde eli "onko P = NP?".

Clay-instituutti lupasi miljoona dollaria tämän ongelman ratkaisemisesta. Vinay Deolalikar väitti ratkaisseensa ongelman 11. elokuuta 2010.[1] Deolalikarin todistus joutui kuitenkin heti kritiikin kohteeksi.[2] Käytännössä pidettiin jo etukäteen todennäköisenä, ettei lause P = NP pidä paikkaansa eikä NP-täydellisille ongelmille siten voida löytää tehokkaita ratkaisualgoritmeja nykyisenkaltaisille tietokoneille.

Lähteet[muokkaa | muokkaa wikitekstiä]

  1. http://www.theregister.co.uk/2010/08/11/the_p_versus_np_problem/
  1. http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf
  2. http://www.newscientist.com/article/dn19313-tide-turns-against-milliondollar-maths-proof.html?DCMP=OTC-rss&nsref=physics-math
Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.