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 18:23, 5 April 2006 (def of non-uniform given). 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 missing: row convexity + ???

Definition of uniform and non-uniform csp in terms of the homomorphism problem. Based on this definition:

  • dichotomy theorems for non-uniform problems: case with domain of size 3 (Bulatov)
  • 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) 18:23, 5 April 2006 (UTC)[reply]

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