In this thesis we study Boolean functions from three different perspectives. First, we study the complex- ity of Boolean minimization for several classes of formulas with polynomially solvable SAT, and formulate sufficient conditions for a class which cause the minimization problem to drop at least one level in the polyno- mial hierarchy. Second, we study a class of matched CNFs for which SAT is trivial but minimization remains Σp 2 complete. We prove that every matched CNF has at least one equivalent prime and irredundant CNF that is also matched. We use this fact to prove the main result of this part, namely that for every matched CNF all clause minimal equivalent CNFs are also matched. Third, we look at propagation completeness - the property of a CNF that says that for every partial assignment all entailed literals can be discovered by unit propagation. We can extend every CNF to be propagation complete by adding empowering impli- cates to it. The main result of this section is a the proof of coNP completeness of the recognition problem for propagation complete CNFs. We also show that there exist CNFs to which an exponential number of empowering implicates have to be added to make them propagation complete.
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:332373 |
| Date | January 2014 |
| Creators | Gurský, Štefan |
| Contributors | Čepek, Ondřej, Marquis, Pierre, Janota, Mikoláš |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0014 seconds