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
[szerkesztés]Döntési probléma
[szerkesztés]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
[szerkesztés]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
[szerkesztés]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
[szerkesztés]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
[szerkesztés]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
[szerkesztés]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
[szerkesztés]- 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
[szerkeszté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.