UNIBZ KRDB Internal SeminarsAccording to requests of people, attended KRDB seminar on Monday, June 3d, I decided to make next KRDB seminar totally devoted to

applications of "post lattice theory" (

dichotomy results for SAT and circuit problems, tractable case of

conjunctive query containment,

expressive power of constraints).

Time: Wednesday, July 20th, 2005, 14:00

Speaker: Andrei Lopatenko

Topic: Post Lattice and Complexity TheoryAbstract: Exposition of application of a theory of boolean functions to complexity theory. The emphasize is on obtaining dichotomy results.

The following theorems and their proofs will be presented in full details :

1) [RW00] The complexity of CIRCUIT-SAT(B) problem (the problem is NP-hard if S_1 \subseteq [b], in all other cases it is PTIME solvable)

1a) Corollary of 1) LEwis theorem: SAT(B) is NP-hard if S_1 \subseteq B; in all other cases it is in PTIME

2) [RW00] CVP(B) is in NC if B \subseteq V \cup L \cup E; in all other cases it is PTIME-hard

3) [KV00] Schaefer Theorem (exposition will be given through algebraic approach proposed in KV00): CSP(B) is in PTIME, if B is a Schaefer structure; in all other cases CSP(B) is NP-hard

3) Corollary of 3). [Kv00] Testing whether a two-atom conjunctive query is contained in a conjunctive query can be done in PTIME

4)[JCS99] Other characterizations of tractable fragments of SAT

CIRCUIT-SAT is Circuit Satisfiability

CVP is Circuit Value Problem

CSP is Constraint Satisfaction PRoblem

RW00 Reigt Wagner, The complexity of problems defined by Boolean circuits, TR,

http://haegar.informatik.uni-wuerzburg.de/personen/ehemalig/streit/TRs/re-wa00.html

KV00 P. Kolaitis, M. Vardi, Conjunctive query containment and constraint satisfaction, JCSS 2000

http://www.cse.ucsc.edu/~kolaitis/papers/pods98f7.ps

JCG99 Jeavons Cohen Gyssens How to determine an expressive power of constraints, Constraints 1999

http://www.cs.rhul.ac.uk/research/constraints/publications/pubs-ps/how_to_determine.ps

BCRV42 Bohler, Creignou, Reith, Vollmer Playing with Boolean Blocks: Post's Lattice with Application to Complexity Theory, SIGACT NEWS Complexity Theory Column 42

BCRV43 Bohler, Creignou, Reith, Vollmer Playing with Boolean Blocks: Constraint Satisfaction Problems, SIGACT NEWS Complexity Theory Column 43