On the Complexity of Monotone Boolean Duality Testing

Elbassioni, Khaled

Lokale TagsFreigabegeschichteDetailsÜbersicht

On the Complexity of Monotone Boolean Duality Testing

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

Item is Freigegeben

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:

Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-E4CA-2 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-E4CC-D

Genre: Bericht

Latex : On the Complexity of Monotone {Boolean} Duality Testing

ausblenden:

Urheber:
Elbassioni, Khaled¹, Autor

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

Inhalt

einblenden:

ausblenden:

Schlagwörter: -

Zusammenfassung: 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.