(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}.)

You may consider stopping adding an invitation to register to conferences in every post. This is distracting and somewhat boring.

ReplyDeleteAnon 1: Don't read tommorows

ReplyDeletecolumn since it will

have a very distracting and

boring one-line at the top about registering for the complexity conference.

That will be the last day

I do that, so you can

resume reading after that.

Bill `I almost never comment

on my own blog' Gasarch