Jump to content

Talk:Complexity of constraint satisfaction

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Tizio (talk | contribs) at 14:06, 5 April 2006 (something done). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Missing:

  • Jeavons et al. approach (Dechter, articles [34,35,36] in Vardi)
  • tree decomposition and similar: query decompositio, hyper-tree decomposition; LOGCFL
  • conditions based on local consistency

Definition of uniform and non-uniform csp; it can be given in terms of the homomorphism problem: the second set of structures comprises a single one; it is equivalent to a fixed domain and relations; therefore, it is a form of relational restriction where a single specific domain and a specific set of relations are allowed. Based on this definition:

  • dichotomy theorems for non-uniform problems: for which structures B is the problem P/NP-hard? is the problem always either P or NP-hard for a given set of structures B? (Schaefer for binary domains, Hell and Nesetril for undirected graphs, where P=graph is bipartite, or bicolorable, it's the same)
  • sufficient general conditions for non-uniform (=fixed B): negation expressible in Datalog; similar condition for uniform

Relation with other formalisms: join of relations, conjuntive query evaluation/containment, pebble game (relation with strong k-consistency), datalog, datalog uniform, query rewriting

- Liberatore(T) 15:32, 1 April 2006 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Complexity_of_constraint_satisfaction&oldid=47093336"