(Complexity Conference next week!

Register Here)

(Guest Post by Manuel Bodirsky on a paper of his that applies
Ramsey Theory.)

In a

recent paper
we apply the so-called product
Ramsey theorem to classify the computational complexity of a large
class of constraint satisfaction problems.

A *temporal constraint language* is a relational structure &Gamma
with a first-order definition in (Q,<), the linear order of the rational
numbers. The problem CSP(&Gamma) is the following computational problem.
Input: A *primitive positive* first-order sentence, that is, a
first-order sentence that is built from existential quantifiers and
conjunction, but without universal quantification, disjunction, and
negation.
Question: Is the given sentence true in &Gamma?

In our paper we show that such a problem is NP-complete
unless &Gamma is from one out of nice classes where the problem
can be solved in polynomial time.

The statement of the product Ramsey theorem that we use is
as follows: for all positive integers d, r, m, and k > m,
there is a positive integer R
such that for all sets S

_{1},...,S

_{d} of size at least R
and an arbitrary coloring of the
[m]

^{d} subgrids of
S

_{1} × ... × S

_{d}
with r colors,
there exists a [k]

^{d} subgrid of
S

_{1} × ... × S

_{d}
such that all [m]

^{d} subgrids of the [k]

^{d}
subgrid have the same color.
(A [k]

^{d}-subgrid of
S

_{1} × ... × S

_{d}
is a subset of
S

_{1} × ... × S

_{d}
of the form
S

_{1'} × ... × S

_{d'},
where
S

_{i'} is a k-element subset of S

_{i}.)

--

Posted By GASARCH to

Computational Complexity at 6/19/2008 07:40:00 AM