On the Complexity of Monotone Boolean Duality Testing

Elbassioni, Khaled

Local TagsRelease HistoryDetailsSummary

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 Released

show all hide all

Basic

show hide

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

Genre: Report

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

Files

show Files

Locators

show

Creators

show

hide

Creators:
Elbassioni, Khaled¹, Author

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

Content

show

hide

Free keywords: -

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.

Details

show

hide

Language(s): eng - English

Dates: Date issued: 2006

Publication Status: Issued

Pages: -

Publishing info: Piscataway, NJ : DIMACS

Table of Contents: -

Rev. Type: -

Identifiers: Report Nr.: DIMACS TR: 2006-01
BibTex Citekey: Elbassioni2006

Degree: -

Event

show

Legal Case

show

Project information

show

Source

show