25 citations · 26 across the 4 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2010
Complexity of Homogeneous Co-Boolean Constraint Satisfaction Problems
Florian Richoux
Constraint Satisfaction Problems (CSP) constitute a convenient way to capture many combinatorial problems. The general CSP is known to be NP-complete, but its complexity depends on…
cs.CC2010★ 1 cited
Complexity of Existential Positive First-Order Logic
Manuel Bodirsky, Miki Hermann, Florian Richoux
Let gamma be a (not necessarily finite) structure with a finite relational signature. We prove that deciding whether a given existential positive sentence holds in gamma is in Logs…