Výpočtový problém - Computational problem - Wikipedia

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Říjen 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teoretická informatika, a výpočetní problém je problém, který a počítač může být schopen vyřešit nebo otázku, na kterou může být počítač schopen odpovědět. Například problém factoring

"Bylo zadáno kladné celé číslo n, najděte netriviální primární faktor n."

je výpočetní problém. Na výpočetní problém lze pohlížet jako na nekonečnou sbírku instance spolu s, případně prázdným, soubor z řešení pro každý případ. Například v problémovém faktoringu jsou instance celá čísla na řešení jsou prvočísla p které popisují netriviální hlavní faktory n.

Výpočtové problémy jsou jedním z hlavních předmětů studia v teoretické informatice. Pole teorie výpočetní složitosti pokusy určit množství zdrojů (výpočetní složitost ) řešení daného problému bude vyžadovat a vysvětlit, proč některé problémy jsou nepoddajný nebo nerozhodnutelný. Výpočtové problémy patří třídy složitosti které obecně definují zdroje (např. čas, prostor / paměť, energii, hloubku obvodu) potřebné k jejich výpočtu (řešení) pomocí různých abstraktní stroje (např. klasický nebo kvantová stroje).

Pro mnoho problémů je typické reprezentovat instance i řešení binárně struny, jmenovitě prvky {0, 1}^* (vidět regulární výrazy pro použitou notaci). Například čísla lze reprezentovat jako binární řetězce pomocí binárního kódování.

Kvůli čitelnosti někdy v následujících příkladech identifikujeme čísla pomocí jejich binárních kódování.

Druhy výpočtových problémů

A rozhodovací problém je výpočetní problém, kde odpověď pro každou instanci je buď ano nebo ne. Příkladem rozhodovacího problému je testování primality:

"Bylo zadáno kladné celé číslo n, zjistit, zda n je hlavní. “

Rozhodovací problém je obvykle reprezentován jako sada všech instancí, pro které je odpověď Ano. Například testování primality může být reprezentováno jako nekonečná množina

L = {2, 3, 5, 7, 11, ...}

V problém s hledáním, odpověďmi mohou být libovolné řetězce. Například factoring je problém hledání, kde instance jsou (řetězcové reprezentace) kladných celých čísel a řešení jsou (řetězcové reprezentace) kolekce prvočísel.

Problém hledání je reprezentován jako vztah skládající se ze všech párů instance-řešení, nazývaných a relace vyhledávání. Například factoring může být reprezentován jako vztah

R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5)...}

které se skládají ze všech dvojic čísel (n, p), kde p je netriviální primární faktor n.

A počítání problém požaduje počet řešení daného vyhledávacího problému. Například problém počítání spojený s factoringem je

"Bylo zadáno kladné celé číslo n, spočítat počet netriviálních hlavních faktorů n."

Problém s počítáním může být reprezentován funkcí F od {0, 1}^* na nezáporná celá čísla. Pro vyhledávací vztah R, problém počítání spojený s R je funkce

F_R(x) = | {y: R(X, y) }|.

An optimalizační problém žádá o nalezení „nejlepšího možného“ řešení ze souboru všech možných řešení problému hledání. Jedním z příkladů je maximální nezávislá sada problém:

„Vzhledem k grafu G, najít nezávislá sada z G maximální velikosti. "

Problémy s optimalizací mohou být reprezentovány jejich vyhledávacími vztahy.

V funkční problém jediný výstup (a celková funkce ) se očekává pro každý vstup, ale výstup je složitější než výstup a rozhodovací problém, to znamená, že to není jen „ano“ nebo „ne“. Jedním z nejslavnějších příkladů je obchodní cestující problém:

„Vzhledem k seznamu měst a vzdálenostem mezi každou dvojicí měst najděte nejkratší možnou trasu, která navštíví každé město přesně jednou a vrátí se do původního města.“

Je to NP-tvrdé problém v kombinatorická optimalizace, důležité v operační výzkum a teoretická informatika.

Slibný problém

v teorie výpočetní složitosti, obvykle se implicitně předpokládá, že jakýkoli řetězec v {0, 1}^* představuje instanci daného výpočetního problému. Někdy však ne všechny řetězce {0, 1}^* představují platné instance a jedna určuje správnou podmnožinu {0, 1}^* jako sada „platných instancí“. Výpočtové problémy tohoto typu se nazývají slibovat problémy.

Následuje příklad problému s (rozhodovacím) slibem:

„Vzhledem k grafu G, zjistit, jestli každý nezávislá sada v G má velikost nejvýše 5, nebo G má nezávislou sadu velikosti alespoň 10. "

Zde jsou platné instance ty grafy, jejichž maximální nezávislá velikost sady je buď maximálně 5, nebo alespoň 10.

Problémy s rozhodovacím slibem jsou obvykle reprezentovány jako dvojice nesouvislých podmnožin (L_Ano, L_Ne) z {0, 1}^*. Platné instance jsou ty v L_Ano ∪ L_Ne.L_Ano a L_Ne představují instance, jejichž odpověď je Ano a Ne, resp.

Slibné problémy hrají důležitou roli v několika oblastech EU výpočetní složitost, počítaje v to tvrdost aproximace, testování vlastností, a interaktivní kontrolní systémy.

Viz také

• Boční výpočty, alternativní přístupy k řešení problémů výpočetně

Reference

• Dokonce, Šimone; Selman, Alan L .; Yacobi, Yacov (1984), „Složitost problémů slibů u aplikací pro kryptografii veřejného klíče“, Informace a kontrola, 61 (2): 159–173, doi:10.1016 / S0019-9958 (84) 80056-X.
• Goldreich, Oded (2008), Výpočetní složitost: koncepční perspektiva, Cambridge University Press, ISBN  978-0-521-88473-0.
• Goldreich, Oded; Wigderson, Avi (2008), „IV.20 Výpočetní složitost“, in Gowers, Timothy; Barrow-Green, červen; Vůdce, Imre (eds.), Princetonský společník matematiky, Princeton University Press, str. 575–604, ISBN  978-0-691-11880-2.