Concepedia

The Complexity of Equality Constraint Languages

Manuel Bodirsky, Jan Kára

Theory of Computing Systems · 2007 · 78 citations · 15 references

DOI

Concepts

References

15

NP is as easy as detecting unique solutions

Leslie G. Valiant, Vijay V. Vazirani · Theoretical Computer Science · 1986 · 659 citations

, , +4

Classifying the Complexity of Constraints Using Finite Algebras

Andreĭ A. Bulatov, Peter Jeavons, Andrei Krokhin · SIAM Journal on Computing · 2005 · 580 citations · Full text

, , +17

Closure properties of constraints

Peter Jeavons, David A. Cohen, Marc Gyssens · Journal of the ACM · 1997 · 498 citations · Full text

, , +12

Reasoning about temporal relations

Bernhard Nebel, Hans-Jürgen Bürckert · Journal of the ACM · 1995 · 407 citations · Full text

, , +15

Closed systems of functions and predicates

David Geiger · Pacific Journal of Mathematics · 1968 · 278 citations · Full text

, , +16