Parameterized Complexity of Weighted Satisfiability Problems : Decision, Enumeration, Counting

• Autorzy: Creignou N. , Vollmer H.

Identyfikatory

DOI

10.3233/FI-2015-1159

• Języki publikacji: EN

Abstrakty

EN

We consider the weighted satisfiability problem for Boolean circuits and propositional formulæ, where the weight of an assignment is the number of variables set to true. We study the parameterized complexity of these problems and initiate a systematic study of the complexity of its fragments. Only the monotone fragment has been considered so far and proven to be of same complexity as the unrestricted problems. Here, we consider all fragments obtained by semantically restricting circuits or formulæ to contain only gates (connectives) from a fixed set B of Boolean functions. We obtain a dichotomy result by showing that for each such B, the weighted satisfiability problems are either W[P]-complete (for circuits) or W[SAT]-complete (for formulæ) or efficiently solvable. We also consider the related enumeration and counting problems.

Słowa kluczowe

EN

parameterized complexity; weighted satisfiability; parameterized counting complexity; polynomial-delay enumeration; Post’s lattice

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 4
• Strony: 297--316
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Creignou N.

• Aix-Marseille Université, CNRS, LIF UMR 7279 13288, Marseille, France

autor

Vollmer H.

• Institut für Theoretische Informatik, Leibniz Universität Hannover Appelstr. 4, 30167 Hannover, Germany

Bibliografia

• [1] Abrahamson, K. R., Downey, R., Fellows, M.: Fixed-Parameter Tractability and Completeness IV: On Completeness for W[P] and PSPACE Analogues, Annals of Pure and Applied Logic, 73(3), 1995, 235–276.
• [2] Bauland, M., Schneider, T., Schnoor, H., Schnoor, I., Vollmer, H.: The Complexity of Generalized Satisfiability for Linear Temporal Logic, Logical Methods in Computer Science, 5(1), 2008.
• [3] Böhler, E., Creignou, N., Galota, M., Reith, S., Schnoor, H., Vollmer, H.: Boolean Circuits as a Data Structure for Boolean Functions: Efficient Algorithms and Hard Problems, Logical Methods in Computer Science, 8(3), 2010.
• [4] Böhler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean Blocks I: Post’s lattice with applications to complexity theory, SIGACT News, 34(4), 2003, 38–52.
• [5] Creignou, N., A.Meier, Vollmer, H., Thomas, M.: The Complexity of Reasoning for Fragments of Autoepistemic Logic, ACM Trans. Comput. Log., 13(2), 2012, 17.
• [6] Creignou, N., Meier, A., Müller, J.-S., Schmidt, J., Vollmer, H.: Paradigms for Parameterized Enumeration, Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, 8087, Springer, 2013.
• [7] Creignou, N., Schnoor, H., Schnoor, I.: Nonuniform Boolean constraint satisfaction problems with cardinality constraint, ACM Trans. Comput. Log., 11(4), 2010.
• [8] Flum, J., Grohe, M.: The Parameterized Complexity of Counting Problems, SIAM J. Comput., 33(4), 2004, 892–922.
• [9] Flum, J., Grohe, M.: Parameterized Complexity Theory, Springer, 2006.
• [10] Kratsch, S., Marx, D.,Wahlström, M.: Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems, Mathematical Foundations of Computer Science 2010, 35th International Symposium, 6281, Springer, 2010.
• [11] Lewis, H.: Satisfiability problems for propositional calculi, Mathematical Systems Theory, 13, 1979, 45–53.
• [12] Marx, D.: Parameterized complexity of constraint satisfaction problems, Computational Complexity, 14(2), 2005, 153–183.
• [13] McCartin, C.: Parameterized counting problems, Annals of Pure and Applied Logic, 138(1-3), 2006, 147–182.
• [14] Niedermeier, R.: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.
• [15] Post, E.: The two-valued iterative systems of mathematical logic, Annals of Mathematical Studies, 5, 1941, 1–122.
• [16] Reith, S., Wagner, K.: The complexity of problems defined by Boolean circuits, Proceedings Mathematical Foundation of Informatics (MFI99), World Science Publishing, 2005.
• [17] Schnoor, H.: The Complexity of Model Checking for Boolean Formulas, Int. J. Found. Comput. Sci., 21(3), 2010, 289–309.
• [18] Thomas, M.: On the applicability of Post’s lattice, Information Processing Letters, 112(10), 2012, 386–391.
• [19] Vollmer, H.: Introduction to Circuit Complexity, Springer Verlag, Berlin Heidelberg, 1999.