Néhány szakkörön át olyan feladatokat nézünk meg, amelyekről közismert, hogy nagy bemenet esetén nem oldhatók meg. (Picit pontosabban a P != NP sejtés teljesülése esetén következik, hogy nem létezik polinomiális megoldó algoritmus. Ennek részleteiről egy későbbi alkalommal lesz szó.)
Az ilyen feladatokkal is érdemes foglalkozni, például a következők miatt: - Annak ellenére, hogy nem létezik polinomiális megoldó algoritmus, nem túl nagy bemenetre még lehet remény hatékony programot írni.
- Előfordulhat, hogy az elméleti korlát igaz, de a gyakorlatban előforduló esetekben vannak olyan plusz korlátozások, amelyek mellett már hatékonyan kezelhető a feladat.
- Néha annak is örülünk, ha az optimálisnál nem sokkal rosszabb közelítő megoldást találunk.
- A véletlen felhasználásával bizonyos esetekben nagyon-nagy valószínűséggel megtaláljuk a jó megoldást.
Feladat |