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.[1] 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.[2] Lielākā daļa zinātnieku un pētnieku uzskata, ka P≠NP.[3]
Atsauces
[labot šo sadaļu | labot pirmkodu]- ↑ «Diskrētā matemātika». enciklopedija.lv. Skatīts: 2020. gada 1. februārī.
- ↑ Lance Fortnow. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton, NJ : Princeton University Press, 2013. ISBN 9780691156491.
- ↑ «Guest Column: The Third P =? NP Poll1».
 | Šis ar informācijas tehnoloģijām saistītais raksts ir nepilnīgs. Jūs varat dot savu ieguldījumu Vikipēdijā, papildinot to. |
 | Šis ar matemātiku saistītais raksts ir nepilnīgs. Jūs varat dot savu ieguldījumu Vikipēdijā, papildinot to. |