Pubblicazioni

Autori:

Raffaele, Alice; Rizzi, Romeo

Titolo:

New theoretical results on the Monotone Boolean Duality and the Monotone Boolean Dualization problems

Anno:

2025

Tipologia prodotto:

Articolo in Rivista

Tipologia ANVUR:

Articolo su rivista

Lingua:

Inglese

Referee:

Sì

Nome rivista:

DISCRETE APPLIED MATHEMATICS

ISSN Rivista:

0166-218X

N° Volume:

361

Intervallo pagine:

347-369

Parole chiave:

Monotone Boolean function; Hypergraph transversal; Clutter and blocker; Full cover; Quasi-polynomial time; Dualization

Breve descrizione dei contenuti:

This work presents a new decomposition for the Monotone Boolean Duality problem, which consists of checking whether two monotone Boolean functions f (described by its unique irredundant DNF) and g (described by its unique irredundant CNF) are equivalent. This coNP problem has several applications and relevance in many research areas (e.g., data mining and knowledge discovery, artificial intelligence, matroid theory, computational biology, and, last but not least, mathematical programming). Best-known algorithms run in quasi-polynomial time; no polynomial-time algorithm has been discovered yet, even if for many special classes these are known. The exact complexity of the general problem is still an open question. Based on both classical results by Berge (1989) and Fredman and Khachiyan (1996), and also on the concept of full covers used by Boros and Makino (2009) and Elbassioni (2008), we propose a new approach to decompose the problem and obtain new theoretical results. Our scheme offers a strong bound which, in the worst case only, has the same time complexity as Fredman and Khachiyan (1996). Anyway, it better highlights the inherent symmetry of the problem, lets us present another polynomial-space algorithm for the Monotone Boolean Dualization problem, and motivates further study on full covers. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

Id prodotto:

143138

Handle IRIS:

11562/1146736

ultima modifica:

10 dicembre 2024

Citazione bibliografica:

Raffaele, Alice; Rizzi, Romeo, New theoretical results on the Monotone Boolean Duality and the Monotone Boolean Dualization problems «DISCRETE APPLIED MATHEMATICS» , vol. 361 , 2025 , pp. 347-369

Consulta la scheda completa presente nel repository istituzionale della Ricerca di Ateneo