liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Complexity Dichotomies for CSP-related Problems
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
2007 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Ladner’s theorem states that if PNP, then there are problems in NP that are neither in P nor NP-complete. Csp(Γ) is a class of problems containing many well-studied combinatorial problems in NP. Csp(Γ) problems are of the form: given a set of variables constrained by a set of constraints from the set of allowed constraints Γ, is there an assignment to the variables satisfying all constraints? A famous, and in the light of Ladner’s theorem, surprising conjecture states that there is a complexity dichotomy for Csp(Γ); that is, for any fixed finite Γ, the Csp(Γ) problem is either in P or NP-complete.

In this thesis we focus on problems expressible in the Csp(Γ) framework with different computational goals, such as: counting the number of solutions, deciding whether two sets of constraints have the same set of solutions, deciding whether all minimal solutions of a set of constraints satisfies an additional constraint etc. By doing so, we capture a host of problems ranging from fundamental problems in nonmonotonic logics, such as abduction and circumscription, to problems regarding the equivalence of systems of linear equations. For several of these classes of problem, we are able to give complete complexity classifications and rule out the possibility of problems of intermediate complexity. For example, we prove that the inference problem in propositional variable circumscription, parameterized by the set of allowed constraints Γ, is either in P, coNP-complete, or ΠP/2-complete. As a by-product of these classifications, new tractable cases and hardness results for well-studied problems are discovered.

The techniques we use to obtain these complexity classifications are to a large extent based on connections between algebraic clone theory and the complexity of Csp(Γ). We are able to extend these powerful algebraic techniques to several of the problems studied in this thesis. Hence, this thesis also contributes to the understanding of when these algebraic techniques are applicable and not.

Place, publisher, year, edition, pages
Institutionen för datavetenskap , 2007. , 36 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1091
Keyword [en]
Complexity, Constraint Satisfaction Problem, System of Equations, Nonmonotonic Logic, Circumscription, Abduction, Isomorphism
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-8822ISBN: 9789185715206 (print)OAI: oai:DiVA.org:liu-8822DiVA: diva2:23528
Public defence
2007-06-01, Visionen, Hus B, Campus Valla, Linköping University, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2007-05-03 Created: 2007-05-03 Last updated: 2017-12-12Bibliographically approved
List of papers
1. The Complexity of Counting Solutions to Systems of Equations over Finite Semigroups
Open this publication in new window or tab >>The Complexity of Counting Solutions to Systems of Equations over Finite Semigroups
2004 (English)In: Proceedings of the 10th Annual International Conference on Computing and Combinatorics (COCOON-2004), Jeju Island, Korea, Springer , 2004, 370-379 p.Conference paper, Published paper (Other academic)
Place, publisher, year, edition, pages
Springer, 2004
Series
Lecture Notes in Computer Science, 3106
National Category
Engineering and Technology Computer Science
Identifiers
urn:nbn:se:liu:diva-14451 (URN)3-540-22856-X (ISBN)
Available from: 2007-05-03 Created: 2007-05-03 Last updated: 2017-02-23
2. The Complexity of Equivalence and Isomorphism of Systems of Equations over Finite Groups
Open this publication in new window or tab >>The Complexity of Equivalence and Isomorphism of Systems of Equations over Finite Groups
2005 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 345, no 2-3, 406-424 p.Article in journal (Refereed) Published
Abstract [en]

We study the computational complexity of the isomorphism and equivalence problems on systems of equations over a fixed finite group. We show that the equivalence problem is in P if the group is Abelian, and coNP-complete if the group is non-Abelian. We prove that if the group is non-Abelian, then the problem of deciding whether two systems of equations over the group are isomorphic is coNP-hard. If the group is Abelian, then the isomorphism problem is GRAPH ISOMORPHISM-hard. Moreover, if we impose the restriction that all equations are of bounded length, then we prove that the isomorphism problem for systems of equations over finite Abelian groups is GRAPH ISOMORPHISM-complete. Finally, we prove that the problem of counting the number of isomorphisms of systems of equations is no harder than deciding whether there exist any isomorphisms at all.

Keyword
Graph isomorphism; Computational complexity; Systems of equations; Finite groups
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-14452 (URN)10.1016/j.tcs.2005.07.018 (DOI)
Available from: 2007-05-03 Created: 2007-05-03 Last updated: 2009-05-28
3. An Algebraic Approach to the Complexity of Propositional Circumscription
Open this publication in new window or tab >>An Algebraic Approach to the Complexity of Propositional Circumscription
2004 (English)In: Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS-2004), Turku, Finland, 2004, 367-376 p.Conference paper, Published paper (Other academic)
Abstract [en]

Every logical formalism gives rise to two fundamental problems: model checking and inference. Circumscription is one of the most important and well studied formalisms in the realm of nonmonotonic reasoning. The model checking and inference problem for propositional circumscription has been extensively studied from the viewpoint of computational complexity. We use a new approach based on algebraic techniques to study the complexity of the model checking and inference problems for propositional variable circumscription in a unified way. We prove that there exists a dichotomy theorem for the complexity of the inference problem in propositional variable circumscription. We also study the model checking and inference problem for propositional variable circumscription in many-valued logics using the same algebraic techniques. In particular we prove dichotomy theorems for the complexity of model checking and inference for propositional variable circumscription in the case of 3-valued logic.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-14453 (URN)10.1109/LICS.2004.1319631 (DOI)0-7695-2192-4 (ISBN)
Available from: 2007-05-03 Created: 2007-05-03 Last updated: 2017-02-23
4. A Trichotomy in the Complexity of Propositional Circumscription
Open this publication in new window or tab >>A Trichotomy in the Complexity of Propositional Circumscription
2004 (English)In: Proceedings of the 11th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR-2004), Montevideo, Uruguay, 2004, 257-269 p.Conference paper, Published paper (Other academic)
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-14454 (URN)
Available from: 2007-05-03 Created: 2007-05-03 Last updated: 2009-05-28
5. Propositional Abduction is Almost Always Hard
Open this publication in new window or tab >>Propositional Abduction is Almost Always Hard
2005 (English)In: Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-2005), Edinburgh, Scotland, UK, 2005, 534-539 p.Conference paper, Published paper (Other academic)
Abstract [en]

Abduction is a fundamental form of nonmonotonic reasoning that aims at finding explanations for observed manifestations. Applications of this process range from car configuration to medical diagnosis. We study here its computational complexity in the case where the application domain is described by a propositional theory built upon a fixed constraint language and the hypotheses and manifestations are described by sets of literals. We show that depending on the language the problem is either polynomial-time solvable, NP-complete, or Σ P 2-complete. In particular, we show that under the assumption P�=NP, only languages that are affine of width 2 have a polynomial algorithm, and we exhibit very weak conditions for NP-hardness.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-14455 (URN)
Available from: 2007-05-03 Created: 2007-05-03 Last updated: 2009-05-28

Open Access in DiVA

fulltext(298 kB)389 downloads
File information
File name FULLTEXT01.pdfFile size 298 kBChecksum MD5
4630e847e5dd79db7df75ac919e49783febfc95ea8c3249103bde1056aab8f1820b39c27
Type fulltextMimetype application/pdf

Authority records BETA

Nordh, Gustav

Search in DiVA

By author/editor
Nordh, Gustav
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 389 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1532 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf