Publication at Faculty of Mathematics and Physics |
2007
Abstract
In this paper we show, that the problem of finding an interval function, which makes a minimum number of errors for a given partially defined Boolean function is NP-hard if we do not specify the order of variables in advance, and solvable in polynomial time in case of a fixed ordering.