|
|
|
|
|
|
|
|||
| Év szerint | Hónap szerint | Ugrás a hónaphoz | |||||||
Petar Markovic (University of Novi Sad): Quantified CSP via polymorphisms |
|
|||
|
|
||||
|
||||
| Abstract. The [fixed-template] Quantified Constraint Satisfaction Problem (QCSP) is the decision problem of the following type: fix a finite model A in a relational language and input a logical formula, and decide whether the formula holds true in the model. The type of formulae under consideration in QCSP are sentences in prenex form in which the unquantified part is a conjunctions of atomic formulae. We will first review some initial results on QCSP by H. Chen and the recent breakthroughs by D. Zhuk and B. Martin. Then we will elaborate on the approach via the surjective part of the clone of compatible operations proved by F. Börner et al. In the second part of the talk, we will use the approach via surjective polymorphisms to fully classify the complexity of QCSP for semicomplete digraphs (irreflexive, but any distinct pair of vertices has at least one directed edge between them). We will illustrate some of the techniques needed by proving a key lemma, that when the template is a certain 5-vertex digraph which we denote by $K_{2\rightarrow 2}^{+}$, the QCSP problem is Pspace-complete. The results in the second part of the talk are all in the paper by B. Martin, P. Djapic and the speaker. In the end, time permitting, we will discuss some directions for future research along the lines outlined in the semicomplete digraphs case. |
||||
| Hely : Bolyai Intézet, I. emelet, Riesz terem, Aradi Vértanúk tere 1., Szeged | ||||
Esemény exportálása JEvents v3.1.8 Stable Copyright © 2006-2013