Számítási probléma

Az elméleti számítástechnikában a számítási probléma olyan probléma, amely egy algoritmussal megoldható.

Például a faktorizáció problémája: "Adott n pozitív egész szám, keresse meg n nem triviális prímtényezőjét." Ez egy számítási probléma.

A számítási problémát úgy lehet tekinteni, mint példányok vagy esetek halmazát, valamint minden példányra/esetre egy lehetséges üres megoldáskészletet. Például a faktorizációs feladatban a példányok n egész számok, a megoldások pedig p prímszámok, amelyek n nem triviális prímtényezőit írják le.

A számítási problémák az elméleti számítástechnika egyik fő vizsgálati tárgyát képezik. A számítási komplexitás elmélete megkísérli meghatározni, hogy egy adott probléma megoldásához mekkora erőforrás szükséges (számítási komplexitás), és megmagyarázza, hogy egyes problémák miért nem megoldhatók vagy eldönthetők. A számítási problémák bonyolultsági osztályokba sorolhatók, amelyek széles körben határozzák meg azokat az erőforrásokat (pl. idő, tér/memória, energia, áramköri mélység), amelyekre szükség van ahhoz, hogy  különböző absztrakt gépekkel a megoldás kiszámolható legyen. Például a P összetettségi osztály a klasszikus gépeknél, és a BQP a kvantumgépeknél.

Sok problémára jellemző, hogy mind a példányokat, mind a megoldásokat bináris karakterláncokkal ábrázolják, nevezetesen a {0, 1}* [a] elemeivel. Például a számok bináris karakterláncokként ábrázolhatók bináris kódolással.

Típusok

Döntési probléma

A döntési probléma egy számítási probléma, ahol minden esetben a válasz igen vagy nem. Egy példa a döntési problémára a prímtulajdonság teszt: „Adott n pozitív egész szám, határozza meg, hogy n prím-e.”

A döntési probléma jellemzően az összes olyan eset halmazaként jelenik meg, amelyre a válasz igen.

Például a prímtulajdonság teszt végtelen halmazként ábrázolható: L = {2, 3, 5, 7, 11, ...}.

Keresési probléma

Egy keresési feladatban a válaszok tetszőleges karakterláncok lehetnek.

Például a faktorizáció egy keresési probléma, ahol a példányok pozitív egészek (string megjelenítései), a megoldások pedig prímszámok gyűjteményei (string megjelenítései).

A keresési problémát az összes példány-megoldás párból álló relációként ábrázoljuk, amelyet keresési relációnak nevezünk. Például a faktorizáció ábrázolható relációként:

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

amelyek az összes olyan (n, p) számpárból állnak, ahol p az n nemtriviális prímtényezője.

Számlálási probléma

Egy számlálási feladat egy adott keresési feladat megoldásainak számát keresi. Például a faktorizációhoz kapcsolódó számolási probléma: „Adott n pozitív egész szám, számolja meg n nem triviális prímtényezőit.”

Egy számlálási feladat egy f függvénnyel ábrázolható {0, 1} *-tól a nemnegatív egész számokig. R keresési reláció esetén az R-hez kapcsolódó számlálási probléma a fR (x) = | {y: R (x, y)} |függvény.

Optimalizálási probléma

Egy optimalizálási probléma a „lehető legjobb” megoldás megtalálását kéri a keresési probléma összes lehetséges megoldása közül.

Egy példa a maximális független halmaz probléma: „Adott egy G gráf, keressen egy független G maximális méretű halmazt.”

Az optimalizálási problémákat keresési kapcsolataikkal lehet ábrázolni.

Függvényprobléma

Egy függvényproblémában minden bemenethez egyetlen kimenet (egy teljes függvény) várható, de a kimenet összetettebb, mint egy döntési probléma, vagyis nem csak "igen" vagy "nem" lehet.

Az egyik leghíresebb példa az utazó ügynök problémája: „Ha megadja a városok listáját és az egyes várospárok közötti távolságokat, keresse meg a lehető legrövidebb útvonalat, amely pontosan egyszer látogat el minden városba, és visszatér a kiindulási városba.”

Ez egy NP-nehéz probléma a kombinatorikus optimalizálásban, fontos az operációkutatásban és az elméleti számítástechnikában.

Ígéretprobléma

A számítási komplexitás elméletében általában hallgatólagosan feltételezik, hogy a {0, 1} * bármely karakterlánca a kérdéses számítási probléma egy példányát jelenti.

Néha azonban nem minden karakterlánc (0, 1} *) képvisel érvényes példányokat, és egy a(z) {0, 1} * megfelelő részhalmazából adja meg az „érvényes példányok” halmazát.

Az ilyen típusú számítási problémákat ígéretproblémáknak nevezzük.

Példa egy (döntési) ígéretproblémára: „Adott G gráf, határozza meg, hogy G-ben minden független halmaz mérete legfeljebb 5, vagy G-nek van-e legalább 10-es független halmaza." Itt azok a grafikonok érvényesek, amelyek független halmazának maximális mérete legfeljebb 5 vagy legalább 10.

A döntési ígéretproblémát általában a {0, 1} * diszjunkt részhalmazainak (Lyes, Lno) párjaként ábrázolják.

Az érvényes példányok a Lyes ∪ Lno. A Lyes és az Lno azokat az eseteket írja le, amelyek rendre igen, illetve nem.

Az ígéretproblémák fontos szerepet játszanak a számítási összetettség számos területén, beleértve a közelítés szigorúságát, a tulajdonságteszteket és az interaktív bizonyítási rendszereket.

Források

• Even, Shimon; Selman, Alan L.; Yacobi, Yacov (1984), "The complexity of promise problems with applications to public-key cryptography", Information and Control, 61 (2): 159-173, doi: 10.1016 / S0019-9958 (84) 80056-X.
• Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press, ISBN 978-0-521-88473-0.
• Goldreich, Oded; Wigderson, Avi (2008), "IV.20 Computational Complexity", in Gowers, Timothy; Barrow-Green, June; Leader, Imre (szerk.), The Princeton Companion to Mathematics, Princeton University Press, pp. 575–604, ISBN 978-0-691-11880-2.

Fordítás

Ez a szócikk részben vagy egészben a Computational problem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.