The Complexity of Extending a Formula to a MU(1) formula
Daoyun Xu · Journal of Guizhou University · 2005
The extension problem is the question that for a satisfiable CNF formula F whether there exist a formula G such that F+G∈MU(1) with var(G)var(F).It is known that the problem of extending a Horn formula into a MU(1) formula is solvable in polynomial time.But for a general satisfiable CNF formula F,the extension problem is still open.In this paper we will present a algorithm which the complexity is polynomial time of O(n~4) to solve such a question.