The complexity of recursive constraint satisfaction problems

DOI10.1016/J.APAL.2009.07.005MaRDI QIDQ636283zbMATH OpenOpenAlexFDO

Authors Wiktor Marek, Jeffrey Remmel

Publication date 26 August 2011

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2009.07.005

zbMATH Keywords

degrees of solutionsrecursive constraint satisfaction problemsrecursive trees

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Applications of computability and recursion theory (03D80)

Recommendations

• Constraint Satisfaction Problems with Infinite Templates
• Infinite versions of some problems from finite complexity theory
• Maximal Infinite-Valued Constraint Languages
• Maximal infinite-valued constraint languages
• Complexity of infinite-domain constraint satisfaction

Cites work

• Π₀¹-classes and Rado's selection principle
• Automatic Structures: Richness and Limitations
• Convex Programming Methods for Global Optimization
• Degrees of members of \(\Pi_ 1^ 0\) classes
• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• scientific article; zbMATH DE number 3577197 (Why is no real title available?)
• scientific article; zbMATH DE number 1303200 (Why is no real title available?)
• scientific article; zbMATH DE number 1368933 (Why is no real title available?)
• scientific article; zbMATH DE number 3995657 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Logic programs with stable model semantics as a constraint programming paradigm
• On the complexity of cutting-plane proofs
• Principles of Constraint Programming
• The complexity of satisfiability problems
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(5)

• On the complexity of trial and error for constraint satisfaction problems
• The Complexity of theA B CProblem
• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
• scientific article; zbMATH DE number 7199580 (Why is no real title available?)
• The Complexity of the Diagonal Problem for Recursion Schemes

This page was built for publication: The complexity of recursive constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q636283)