P=NP problēma

P=NP problēma ir nozīmīga neatrisināta problēma datorzinātnē. Problēma apzīmē šādu jautājumu: "Vai uzdevums, kura risinājumu ir ātri pārbaudīt, ir arī ātri atrisināms?". Par problēmas pierādījumu vai apgāšanu Kleja Matemātikas institūts (ASV) ir piesolījuši atlīdzību — 1 miljonu ASV dolāru.

Ar vārdu "ātrs" tiek apzīmēts algoritms, kas uzdevumu spēj atrisināt polinomiālā laika posmā (nevis eksponenciālā laika posmā). Šie uzdevumi pieder pie P sarežģītības klases. Ir uzdevumi, kurus nevar atrisināt ātri, savukārt var ātri pārbaudīt, vai konkrētais risinājums ir pareizs. Šādi uzdevumi pieder pie NP klases.

Ja tiktu atrasta pozitīva atbilde uz P=NP problēmu, tas nozīmētu, ka daudzu veidu sarežģītus uzdevumus ir iespējams atrisināt vienkāršāk, nekā to spēj izdarīt pašlaik. Tam būtu liela ietekme matemātikā, kriptogrāfijā, algoritmu izpētē, spēļu teorijā, multimediju apstrādē, filozofijā, ekonomikā un daudzās citās jomās. Lielākā daļa zinātnieku un pētnieku uzskata, ka P≠NP.

 Atsauces 

Kategorija:Datorzinātne