Publikace na Matematicko-fyzikální fakulta |
2005
Abstrakt
Problémem hledání rozšíření částečně definované booleovské funkce rozumíme nalezení booleovské funkce, která správně ohodnocuje daná data. To znamená, že dostaneme dvě množiny booleovských vektorů určující, kde má částečně definovaná funkce hodnotu true a kde false.
A naším úkolem je rozhodnout, zda existuje rozšíření, tedy totální booleovská funkce, která se na zadaných vektorech shoduje s částečně defnovanou booleovskou funkcí. V našem příspěvku ukážeme, že problém nalezení acyklického rozšíření dané částečně definované funkce patří mezi NP-úplné problémy.
Také představíme polynomiální algoritmus rozhodující, zda existuje k-DNF rozšíření (pro pevné k) a dokážeme, že jeho asymptotická časová složitost je optimální.