intractable problem

intractable problem (tsz. intractable problems)

1. (informatika) Informatikai- és matematikai optimalizálásban, algoritmuselméletben intractable (nehezen megoldható) problémának nevezzük azokat a feladatokat, amelyekre jelenleg nem ismerünk polinomiális (tehát „gyors”) algoritmust, és – feltevésünk szerint – nem is létezik ilyen. Ezek a problémák gyakran exponenciális vagy ennél is gyorsabban növekvő futásidejű eljárásokkal oldhatók csak meg, így nagy méretben használhatatlanok.

• Tractable (megoldható/polynomial-time): létezik olyan algoritmus, amely a bemenet méretének (például ${\textstyle n}$ bit, ${\textstyle n}$ csúcs) polinomjában fut le, azaz ${\textstyle O(n^{k})}$ idő alatt.
• Intractable (nehéz megoldású): az ismert algoritmusok futásideje legjobb esetben szuperpolinomiális (például exponenciális ${\textstyle O(2^{n})}$ vagy szuperpolinomális ${\textstyle n^{\log n}}$), és feltehetőleg nincs is polinomikus módszer, azaz a feladat NP-teljes vagy NP-nehéz.

• P: azok a döntési problémák, amelyeket polinomiális idő alatt el tudunk dönteni.
• NP: azok a problémák, amelyekre egy jelölt megoldást polinomiális idő alatt ellenőrizni tudunk.

• Egy probléma NP-teljes, ha
  1. maga is NP-ben van (megoldás igazolása polinomiális időben), és
  2. minden NP-probléma polinom időben redukálható rá.
• Ha egy NP-teljes feladatra polinomiális algoritmust találnánk, akkor minden NP-probléma (tehát az összes NP-teljes is) “megválaszolható” lenne hatékonyan, azaz ${\textstyle P=NP}$.

• Egyik irányban lazább: egy NP-nehéz feladat fog nagyobb vagy ugyanolyan nehézségű lenni, mint bármely NP-probléma, de maga nem feltétlenül van NP-ben (például optimalizációs verzió, vagy döntési verzió hiányzik).

Példák intractable feladatokra

• Travelling Salesman Problem (TSP): minimum súlyú Hamilton-kör keresése.
• Boolean satisfiability (SAT): van-e olyan változó-értékadás, hogy a boole-kifejezés igaz legyen?
• Vertex Cover, Clique, Subset Sum: a korábbiakban áttekintett NP-teljes problémák.

1. Exponenciális algoritmusok – Minden lehetséges részhalmaz, permutáció vagy útvonal kipróbálása.
2. Heurisztikák és közelítő algoritmusok – Greedy-módszerek, lokális keresés, metaheurisztikák (genetikus algoritmusok, szimulált hőkezelés).
3. Approximation (közelítő) séma – FPTAS vagy PTAS: ${\textstyle \varepsilon }$-pontosságot garantál, de még mindig polinom a bemeneti méret és ${\textstyle 1/\varepsilon }$ függvényében.
4. Paraméterezett algoritmusok – A bemeneti adat bizonyos paramétere (például a célösszeg, fa-szélesség) kis értéke esetén hatékony, még ha a teljes méret nagy is.

• PSPACE-teljes: polinomális memóriát igénylő problémák között azokat, amelyek döntése minden PSPACE-problémára redukálható. Gyakran még nehezebbek, mint az NP-teljesek, hisz akár exponenciális időt is felhasználhatnak.
• EXPTIME-teljes: ${\textstyle 2^{\text{polynomial}}}$ időigényű, de polinomiális időn belül nem megoldható feladatok.

Mindhárom kategória intractable-nak számít, de hierarchiájukban NP ⊆ PSPACE ⊆ EXPTIME.

• Dönthetőség (decidability): létezik-e bármilyen algoritmus, akár végtelen idő alatt, ami mindig helyes választ ad?
• Intractability: bármilyen algoritmus csak szuperpolinomiális idő alatt fut.
• Az undecidible feladatok (pl. a Turing-gép leállási problémája) még ennél is rosszabbak: semmilyen algoritmus nem létezik, ami minden esetben dönt.

1. Metszet a valós rendszerekkel – TSP a logisztikában, SAT a hardver-verifikációban, Subset Sum a pénzügyi portfóliókban.
2. Forrásallokáció – Optimalizáló kom­ponensek integrálása nagy rendszerekbe: ha NP-teljes alfeladatok vannak, előtérbe kerülnek közelítő eljárások.
3. Algoritmuskutatás – Az intractable feladatok vezetik a kutatást: keressük a határvonalat P és NP között, fényt derítve a ${\textstyle P{\stackrel {?}{=}}NP}$ kérdésre.

• Intractable problémák olyan feladatok, melyekre polinomiális idő alatt algoritmust nem ismerünk, és valószínűleg nem is létezik.
• Leggyakoribb csoportjuk az NP-teljes és NP-nehéz problémák, de van magasabb szintű intractability (PSPACE, EXPTIME).
• Gyakorlati megoldások: exponenciális algoritmusok, közelítő és heurisztikus eljárások, valamint paraméterezett algoritmusok.
• A téma sarkalatos a számítástudomány alapjainál, és központi a modern algoritmus- és komplexitáselmélet kutatásában.

• intractable problem - Szótár.net (en-hu)
• intractable problem - Sztaki (en-hu)
• intractable problem - Merriam–Webster
• intractable problem - Cambridge
• intractable problem - WordNet
• intractable problem - Яндекс (en-ru)
• intractable problem - Google (en-hu)
• intractable problem - Wikidata
• intractable problem - Wikipédia (angol)