Myslí se tím samozřejmě přibližné řešení, jehož hledání nebude trvat dlouho. Práce se může ubírat několika směry:
Řešitel si vybere nějaký NP-těžký problém, vyhledá publikované algoritmy pro jeho řešení, některé z nich implementuje a otestuje. Cílem práce je zejména seznámit se s metodikou testování a porovnávání optimalizačních algoritmů. Experimentální srovnání je důležitou součástí každého publikovaného článku popisujícího nový algoritmus, proto je třeba, aby studenti, kteří plánují v tomto oboru publikovat, byli se způsoby testování seznámení.
Součástí práce bude návrh a implementace generátoru testovacích problémů, který by měl umožňovat jak generování náhodných instancí, tak "těžkých instancí" (těžkých pro konkrétní řešící algoritmus). Řešitel by měl také navrhnout vlastní řešící algoritmus a zahrnout ho do testování.
Je známo, že NP-úplné problémy jsou navzájem převoditelné. Navíc existují řešiče pro konkrétní třídy problémů (např. SAT-solvery, CSP-solvery, plánovače atd..). Řešitel si vybere některé takové třídy problémů a implementuje převodní algoritmy mezi těmito třídami. Poté otestuje, který řešič (a převodní algoritmus) je nejefektivnější - navrhne baterii testů a spustí různé řešiče pro tyto problémy (s využitím převoditelnosti). Součástí práce bude také návrh převodních algoritmů mezi jednotlivými třídami.
V případě zájmu vysvětlím osobně