Post Lattice and Complexity Theory
UNIBZ KRDB Internal Seminars
According 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 Theory
Abstract: 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
According 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 Theory
Abstract: 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
posted by alopatenko at 6:24 PM
<< Home