About: On the gap between the complexity of SAT and minimization for certain classes of boolean formulas

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: On the gap between the complexity of SAT and minimization for certain classes of boolean formulas Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://www.cs.uic.edu/pub/Isaim2014/WebPreferences/ISAIM2014_Boolean_Cepek_Gursky.pdf
Description	It is a wellknown fact that the satisfiability problem (SAT) for Boolean formulas in a conjunctive normal form (CNF) is NP complete, i.e. 1 complete. It is also known that the decision version of Boolean minimization for CNF inputs is 2 complete. On the other hand there are several subclasses of CNFs (e.g. Horn CNFs) for which SAT is known to be in P = 0 while the minimization problem is 1 complete. Thus, for both the general case and the above mentioned subclasses the gap between the complexity of SAT and minimization is exactly one level in the polynomial hierarchy. There are also some subclasses (e.g. quadratic CNFs) for which there is no gap because both SAT and minimization are in P = 0. In this short note we shall systematically study different classes of Boolean functions with respect to the size of the mentioned gap and show that there also exist classes for which the gap between the complexity of SAT and minimization is the maximum possible (two levels in the polynomial hierarchy). To this end we shall recall a recent result showing that the minimization of the so called matched CNFs is 2 complete. It is a wellknown fact that the satisfiability problem (SAT) for Boolean formulas in a conjunctive normal form (CNF) is NP complete, i.e. 1 complete. It is also known that the decision version of Boolean minimization for CNF inputs is 2 complete. On the other hand there are several subclasses of CNFs (e.g. Horn CNFs) for which SAT is known to be in P = 0 while the minimization problem is 1 complete. Thus, for both the general case and the above mentioned subclasses the gap between the complexity of SAT and minimization is exactly one level in the polynomial hierarchy. There are also some subclasses (e.g. quadratic CNFs) for which there is no gap because both SAT and minimization are in P = 0. In this short note we shall systematically study different classes of Boolean functions with respect to the size of the mentioned gap and show that there also exist classes for which the gap between the complexity of SAT and minimization is the maximum possible (two levels in the polynomial hierarchy). To this end we shall recall a recent result showing that the minimization of the so called matched CNFs is 2 complete. (en)
Title	On the gap between the complexity of SAT and minimization for certain classes of boolean formulas On the gap between the complexity of SAT and minimization for certain classes of boolean formulas (en)
skos:prefLabel	On the gap between the complexity of SAT and minimization for certain classes of boolean formulas On the gap between the complexity of SAT and minimization for certain classes of boolean formulas (en)
skos:notation	RIV/00216208:11320/14:10285647!RIV15-MSM-11320___
http://linked.open...avai/riv/aktivita	I
http://linked.open...avai/riv/aktivity	I
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Čepek, Ondřej Gurský, Štefan
http://linked.open.../riv/druhVysledku	O - Ostatní výsledky nezařaditelné do žádného z výše uvedených druhů výsledku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	34441
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/14:10285647
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	minimization of boolean formulas; complexity of SAT (en)
http://linked.open.../riv/klicoveSlovo	complexity of SAT minimization of boolean formulas
http://linked.open...ontrolniKodProRIV	[CA47D3959C5D]
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...UplatneniVysledku	2014
http://linked.open...iv/tvurceVysledku	Čepek, Ondřej Gurský, Štefan
http://localhost/t...ganizacniJednotka	11320

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 59 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software