Incremental polynomial time dualization of quadratic functions and a subclass of degree‐k functions

Incremental polynomial time dualization of quadratic functions and a subclass of degree‐k functions

0.00 Avg rating0 Votes
Article ID: iaor20117910
Volume: 188
Issue: 1
Start Page Number: 251
End Page Number: 261
Publication Date: Aug 2011
Journal: Annals of Operations Research
Authors:
Keywords: duality
Abstract:

We consider the problem of dualizing a Boolean function f represented by a DNF. In its most general form, this problem is commonly believed not to be solvable by a quasi‐polynomial total time algorithm. We show that if the input DNF is quadratic or is a special degree‐k DNF, then dualization turns out to be equivalent to hypergraph dualization in hypergraphs of bounded degree and hence it can be achieved in incremental polynomial time.

Reviews

Required fields are marked *. Your email address will not be published.