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
The Complexity of Counting Solutions to Systems of Equations over Finite Semigroups
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
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. 370-379 p.
Series
Lecture Notes in Computer Science, 3106
National Category
Engineering and Technology Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-14451ISBN: 3-540-22856-X (print)OAI: oai:DiVA.org:liu-14451DiVA: diva2:23523
Available from: 2007-05-03 Created: 2007-05-03 Last updated: 2017-02-23
In thesis
1. Complexity Dichotomies for CSP-related Problems
Open this publication in new window or tab >>Complexity Dichotomies for CSP-related Problems
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
Complexity, Constraint Satisfaction Problem, System of Equations, Nonmonotonic Logic, Circumscription, Abduction, Isomorphism
National Category
Computer Science
Identifiers
urn:nbn:se:liu:diva-8822 (URN)9789185715206 (ISBN)
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

Open Access in DiVA

No full text

Other links

Link to Ph.D. Thesis

Authority records BETA

Nordh, GustavPeter, Jonsson

Search in DiVA

By author/editor
Nordh, GustavPeter, Jonsson
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Engineering and TechnologyComputer Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 50 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