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 12:29, 1 April 2006 (missing). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Missing:

  • dichotomy theorems for relational restrictions (Schaerf, Hell and Nesetril, other attempts)
  • uniform and non-uniform definition according to the homomorph version of the problem
  • relation with conjuntive query evaluation/containment/pebble games/datalog
  • Jeavons et al. approach (dechter, articles [34,35,36] in Vardi)
  • tree decomposition and others (query decompositio, hyper-tree decomposition)
  • conditions based on local consistency

- Liberatore(T) 12:29, 1 April 2006 (UTC)[reply]

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