The complexity of recursive constraint satisfaction problems

DOI10.1016/j.apal.2009.07.005zbMath1221.03033OpenAlexW2074619587MaRDI QIDQ636283

Victor W. Marek, Jeffery B. 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

recursive treesdegrees of solutionsrecursive constraint satisfaction problems

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of cutting-plane proofs
• Logic programs with stable model semantics as a constraint programming paradigm
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Principles of Constraint Programming
• Π₀¹-classes and Rado's selection principle
• Automatic Structures: Richness and Limitations
• The complexity of satisfiability problems
• Convex Programming Methods for Global Optimization
• ∏ 0 1 Classes and Degrees of Theories