Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Guest Post on App of Ramsey to Constraint Satisfac...

Expand Messages
  • GASARCH
    (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
    Message 1 of 1 , Jun 19, 2008
    • 0 Attachment
      (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 S1,...,Sd of size at least R and an arbitrary coloring of the [m]d subgrids of S1 × ... × Sd with r colors, there exists a [k]d subgrid of S1 × ... × Sd such that all [m]d subgrids of the [k]d subgrid have the same color. (A [k]d-subgrid of S1 × ... × Sd is a subset of S1 × ... × Sd of the form S1' × ... × Sd', where Si' is a k-element subset of Si.)

      --
      Posted By GASARCH to Computational Complexity at 6/19/2008 07:40:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.