„P vs. NP vandamálið“: Munur á milli breytinga

Úr Wikipediu, frjálsa alfræðiritinu
Efni eytt Efni bætt við
JYBot (spjall | framlög)
m r2.7.1) (Vélmenni: Bæti við: az:P=NP
Addbot (spjall | framlög)
m Bot: Flyt 23 tungumálatengla, sem eru núna sóttir frá Wikidata á d:q746242
Lína 9: Lína 9:


[[Flokkur:Óleyst vandamál í tölvunarfræði]]
[[Flokkur:Óleyst vandamál í tölvunarfræði]]

[[ar:مسألة P=NP]]
[[az:P=NP]]
[[ca:P versus NP]]
[[cs:Problém P versus NP]]
[[de:P-NP-Problem]]
[[en:P versus NP problem]]
[[eo:Demando P = NP]]
[[es:Clases de complejidad P y NP]]
[[fa:مسئله برابری پی و ان‌پی]]
[[fi:P=NP]]
[[fr:Problème P = NP]]
[[it:Classi di complessità P e NP]]
[[ja:P≠NP予想]]
[[ko:P-NP 문제]]
[[pt:P versus NP]]
[[ru:Равенство классов P и NP]]
[[simple:P versus NP]]
[[sr:П = НП проблем]]
[[sv:P=NP?]]
[[th:กลุ่มความซับซ้อน พี และ เอ็นพี]]
[[tr:P ile NP arasındaki ilişki]]
[[uk:Рівність класів P і NP]]
[[zh:P/NP问题]]

Útgáfa síðunnar 9. mars 2013 kl. 10:48

P=NP-vandamálið er eitt mikilvægasta opna vandamál innan tölvunarfræðinnar,[1] sem spyr óformlega hvort það sé auðvelt fyrir tölvur að leysa þau vandamál sem er auðvelt að staðfesta svarið á. Vandamálið var kynnt til sögunnar árið 1971 af Stephen Cook.

Ákveðið vandamál tilheyrir flækjustigsflokkinum P ef hægt er að leysa það auðveldlega og það tilheyrir flækjustigsflokkinum NP ef hægt er að staðfesta uppgefna lausn auðveldlega[1] (þar sem auðvelt er óformlega notað þegar fjölda aðgerða er af margliðustærðargráðu miðað við inntakið).

Hlutasummuvandamálið (e. subset sum problem) er dæmi um vandamál þar sem það er auðvelt að staðfesta uppgefna lausn en mögulega erfitt að finna lausn. Er til dæmis einhver hlutmengi {−2, −3, 15, 14, 7, −10} sem hefur summuna 0? Hægt er að staðfesta lausnina {−2, −3, −10, 15} auðveldlega með þremur samlagningum, en það er ekkert þekkt reiknirit sem finnur slíkt hlutmengi sem er í P: slíkt reiknirit getur aðeins verið til ef P = NP.

Tilvísanir

  1. 1,0 1,1 „Hvað felst í vandamálinu ,,P vs. NP?“. Vísindavefurinn.