P=NP problēma

Vikipēdijas lapa
Jump to navigation Jump to search

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]

  1. «Diskrētā matemātika». enciklopedija.lv. Skatīts: 2020. gada 1. februārī.
  2. Lance Fortnow. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton, NJ : Princeton University Press, 2013. ISBN 9780691156491.
  3. «Guest Column: The Third P =? NP Poll1».