On the Complexity of Monotone Boolean Duality Testing

Elbassioni, Khaled

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

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 公開

表示: 全項目非表示: 全項目

基本情報

表示: 非表示:

アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0019-E4CA-2 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0019-E4CC-D

資料種別: 報告書

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

ファイル

表示: ファイル

作成者

表示:

非表示:

作成者:
Elbassioni, Khaled¹, 著者

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

内容説明

表示:

非表示:

キーワード: -

要旨: 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.

資料詳細

表示:

非表示:

言語: eng - English

日付: 出版: 2006

出版の状態: 出版

ページ: -

出版情報: Piscataway, NJ : DIMACS

目次: -

査読: -

識別子（DOI, ISBNなど）: Reportnr.: DIMACS TR: 2006-01
BibTex参照ID: Elbassioni2006

学位: -

アイテム詳細

基本情報

ファイル

関連URL

作成者

内容説明

資料詳細

関連イベント

訴訟

Project information

出版物