P=NP-problemet

Frå Wikipedia – det frie oppslagsverket
Gå til: navigering, søk

P=NP-problemet er eit stort uløyst problem innan informatikken og matematikken og går ut på om dei to kompleksitetsklassene P og NP er like eller ikkje. Problemet er kjent som eit av dei sju millenniumsproblema innan matematikken med ein utlova dusør på 1 million dollar for ei løysing på problemet. Det finst fleire måtar å sjå problemstillinga på. Ei uformell skildring av problemet er følgjande; om det finst ein effektiv måte å sjekka om ei løysing er korrekt, finst det da òg ei effektiv måte å finna ei løysing på problemet. Problemet vart fyrst formulert av Stephen Cook i 1971. Trass mykje forsking på problemet finst det per dags dato inkje bevis for korkje at dei er like eller forskjellige.