Abstrakt
The problem of finding an extension of a partially defined Boolean function (pdBf) is the problem of finding a Boolean function, which correctly classifies given data. That means that in general we are given two sets of Boolean vectors - truepoints and falsepoints - and we want to decide if there exists an extension - a Boolean function, that on all given truepoints has function value true and on all given falsepoints has function value false.
In the case of positive answer we also want to find some representation of some extension. In our contribution we will show that it is NP-complete to decide whether there exists an acyclic extension for a given pdBf.
We will also present a polynomial algorithm for finding a k-DNF extension (for fixed k) and prove that with respect to asymptotic time complexity it is the optimal procedure for solving this problem.