Dichotomy Theorem for the Generalized Unique Satisfiability Problem

Laurent Juban 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The unique satisfiability problem, that asks whether there exists a unique solution to a given propositional formula, was extensively studied in the recent years. This paper presents a dichotomy theorem for the unique satisfiability problem, partitioning the instances of the problem between the polynomial-time solvable and coNP-hard cases. We notice that the additional knowledge of a model makes this problem coNP-complete. We compare the polynomial cases of unique satisfiability to the polynomial cases of the usual satisfiability problem and show that they are incomparable. This difference between the polynomial cases is partially due to the necessity to apply parsimonious reductions among the unique satisfiability problems to preserve the number of solutions. In particular, we notice that the unique not-all-equal satisfiability problem, where we ask whether there is a unique model such that each clause has at least one true literal and one false literal, is solvable in polynomial time.
Type de document :
Communication dans un congrès
Gabriel Ciobanu & Gheorghe Paun. 12th International Symposium on Fundamentals of Computation Theory - FCT'99, 1999, Iasi, Romania, Springer-Verlag, 1684, pp.327-337, 1999, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00099003
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:41:09
Dernière modification le : jeudi 11 janvier 2018 - 06:19:58

Identifiants

  • HAL Id : inria-00099003, version 1

Collections

Citation

Laurent Juban. Dichotomy Theorem for the Generalized Unique Satisfiability Problem. Gabriel Ciobanu & Gheorghe Paun. 12th International Symposium on Fundamentals of Computation Theory - FCT'99, 1999, Iasi, Romania, Springer-Verlag, 1684, pp.327-337, 1999, Lecture Notes in Computer Science. 〈inria-00099003〉

Partager

Métriques

Consultations de la notice

166