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 arvostelun 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/

Kirjallisuutta[muokkaa | muokkaa wikitekstiä]

  • Fortnow, Lance: Kultainen pääsylippu: P, NP ja mahdottoman tavoittelu. (The Golden Ticket: P, NP, and the Search for the Impossible, 2013.) Suomentanut Kimmo Pietiläinen. Helsinki: Terra cognita, 2014. ISBN 978-952-5697-69-8.
Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.