On the Complexity of Monotone Boolean Duality Testing

Elbassioni, Khaled

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Report

On the Complexity of Monotone Boolean Duality Testing

MPS-Authors

/persons/resource/persons44374

Elbassioni, Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Elbassioni, K.(2006). On the Complexity of Monotone Boolean Duality Testing (DIMACS TR: 2006-01). Piscataway, NJ: DIMACS.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0019-E4CA-2

Abstract

We show that the duality of a pair of monotone Boolean functions in disjunctive normal forms can be tested in polylogarithmic time using a quasi-polynomial number of processors. Our decomposition technique yields stronger bounds on the complexity of the problem than those currently known and also allows for generating all minimal transversals of a given hypergraph using only polynomial space.