Publikace na Matematicko-fyzikální fakulta |
2007
Abstrakt
V tomto článku ukazujeme, že problém nalezení intervalové funkce, která rozšiřuje danou částečně definovanou Booleovskou funkci s minimálním počtem chyb, je NP-těžký, pokud pořadí proměnných není určeno dopředu, a řešitelný v polynomiálním čase, pokud je dáno pevné pořadí.