Open Problems List
Arising from MathsCSP Workshop,Oxford,March2006
Version0.3,April25,2006
characterise1Complexity and Tractability of CSP
Question1.0(The Dichotomy Conjecture)Let B be a relational structure.The problem of deciding whether a given relational structure has a homomorphism to B is denoted CSP(B).
For which(finite)structures is CSP(B)decidable in polynomial time?Is it true that for anyfinite structure B the problem CSP(B)is either decidable in polynomial time or NP-complete?
Communicated by:Tomas Feder&Moshe Vardi(1993) Question1.1A relational structure B is called hereditarily tractable if CSP(B )is tractable for all substructures B of B.Which structures B are hereditarily tractable?
Communicated by:Pavol Hell Question1.2A weak near-unanimity term is defined to be one that satisfies the following identities:f(x,...,x)=x and f(x,y,....y)=f(y,x,y,....y)=...=f(y,...,y,x).
Is CSP(B)tractable for any(finite)structure B which is preserved by a weak near-unanimity term?
Communicated by:Benoit Larose,Matt Valeriote Question1.3A constraint language1S is called globally tractable for a problem P,if P(S)is tractable,and it is called(locally)tractable if for everyfinite L⊆S,P(L)is tractable.
These two notions of tractability do not coincide in the Abduction problem(see talk by Nadia Creignou).
•For which computational problems related to the CSP do these two notions of tractability coincide?
•In particular,do they coincide for the standard CSP decision problem?
Communicated by:Nadia Creignou 1That is,a(possibly infinite)set of relations over somefixed set.
1
Question1.4(see also Question3.5)It has been shown that when a structure B has bounded pathwidth duality the corresponding problem CSP(B)is in the complexity class NL (see talk by Victor Dalmau).Is the converse also true(modulo some natural complexity-theoretic assumptions)?
Communicated by:Victor Dalmau Question1.5Is there a good(numerical)parameterization for constraint satisfaction problems that makes themfixed-parameter tractable?
Question1.6Further develop techniques based on delta-matroids to complete the com-plexity classification of the Boolean CSP(with constants)with at most two occurrences per variable(see talk by Tomas Feder).
Communicated by:Tomas Feder Question1.7Classify the complexity of uniform Boolean CSPs(where both structure and constraint relations are specified in the input).
Communicated by:Heribert Vollmer Question1.8The microstructure graph of a binary CSP has vertices for each variable/value pair,and edges that join all pairs of vertices that are compatible with the constraints.
What properties of this graph are sufficient to ensure tractability?Are there properties that do not rely on the constraint language or the constraint graph individually?
2Approximability and Soft Constraints
Question2.1Is it true that Max CSP(L)is APX-complete whenever Max CSP(L)is NP-hard?
Communicated by:Peter Jonsson Question2.2Prove or disprove that Max CSP(L)is in PO if the core of L is super-modular on some lattice,and otherwise this problem is APX-complete.
The above has been proved for languages with domain size3,and for languages contain-ing all constants by a computer-assisted case analysis(see talk by Peter Jonsson).Develop techniques that allow one to prove such results without computer-assisted analysis.
Communicated by:Peter Jonsson Question2.3For some constraint languages L,the problem Max CSP(L)is hard to approximate better than the random mindless algorithm on satisfiable or almost satisfiable instances.Such problems are called approximation resistant(see talk by Johan Hastad).
Is a single random predicate over Boolean variables with large arity approximation resistant?
What properties of predicates make a CSP approximation resistant?
What transformations of predicates preserve approximation resistance?
Communicated by:Johan Hastad
2
Question2.4Many optimisation problems involving constraints(such as Max-Sat,Max CSP,Min-Ones SAT)can be represented using soft constraints where each constraint is specified by a cost function assigning some measure of cost to each tuple of values in its scope.
Are all tractable classes of soft constraints characterized by their multimorphisms?(see talk by Peter Jeavons)
Communicated by:Peter Jeavons 3Algebra
Question3.1The Galois connection between sets of relations and sets of operations that preserve them has been used to analyse several different computational problems such as the satisfiability of the CSP,and counting the number of solutions.
How can we characterise the computational goals for which we can use this Galois connection?
Communicated by:Nadia Creignou Question3.2For any relational structure B=(B,R1,...,R k),let co-CSP(B)denote the class of structures which do not have a homomorphism to B.It has been shown that the question of whether co-CSP(B)is definable in Datalog is determined by P ol(B),the polymorphisms of the relations of B(see talk by Andrei Bulatov).
Let B be a core,F the set of all idempotent polymorphisms of B and V the variety generated by the algebra(B,F).Is it true that co-CSP(B)is definable in Datalog if and only if V omits types1and2(that is,the local structure of anyfinite algebra in V does not contain a G-set or an affine algebra)?
Communicated by:Andrei Bulatov Question3.3Does every tractable clone of polynomials over a group contain a Mal’tsev operation?
Communicated by:Pascal Tesson Question3.actability of corresponding CSPs)clones of polynomials of semigroups.
Communicated by:Pascal Tesson Question3.5Is it true that for any structure B which is invariant under a near-unanimity operation the problem CSP(B)is in the complexity class NL?Does every such structure have bounded pathwidth duality?(see also Question1.4)
Both results are known to hold for a2-element domain(Dalmau)and for majority operations(Dalmau,Krokhin).
Communicated by:Victor Dalmau,Benoit Larose
3
Question3.6Is it decidable whether a given structure is invariant under a near-unanimity function(of some arity)?
Communicated by:Benoit Larose Question3.7Let L be afixedfinite lattice.Given an integer-valued supermodular func-tion f on L n,is there an algorithm that maximizes f in polynomial time in n if the function f is given by an oracle?
The answer is yes if L is a distributive lattice(see“Supermodular Functions and the Complexity of Max-CSP”,Cohen,Cooper,Jeavons,Krokhin,Discrete Applied Mathemat-ics,2005).More generally,the answer is yes if L is obtained fromfinite distributive lattices via Mal’tsev products(Krokhin,Larose–see talk by Peter Jonsson).The smallest lattice for which the answer is not known is the3-diamond.
Communicated by:Andrei Krokhin Question3.8Find the exact relationship between width and relational width.(It is known that one is bounded if and and only if the other is bounded.)
Also,what types of width are preserved under natural algebraic constructions?
Communicated by:Victor Dalmau 4Logic
Question4.1The(basic)Propositional Circumscription problem is defined as fol-lows:
Input:a propositional formulaφwith atomic relations from a set S,and a clause c.
Question:is c satisfied in every minimal model ofφ?
It is conjectured(Kirousis,Kolaitis)that there is a trichotomy for this problem,that it is
either in P,coNP-complete or inΠP
2,depending on the choice of S.Does this conjecture
hold?
Communicated by:Nadia Creignou Question4.2The Inverse Satisfiability problem is defined as follows: Input:afinite set of relations S and a relation R.
Question:is R expressible by a CNF(S)-formula without existential variables?
A dichotomy theorem was obtained by Kavvadias and Sideri for the complexity of this problem with constants.Does a dichotomy hold without the constants?Are the Schaefer cases still tractable?
Communicated by:Nadia Creignou
4
Question4.3Let LFP denote classes of structures definable infirst-order logic with a least-fixed-point operator,let HOM denote classes of structures which are closed under homomorphisms,and let co-CSP denote classes of structures defined by not having a homomorphism to somefixed target structure.
•Is LFP∩HOM⊆Datalog?
•Is LFP∩co-CSP⊆Datalog?(forfinite target structures)
•Is LFP∩co-CSP⊆Datalog?(forω-categorical target structures)
Communicated by:Albert Atserias,Manuel Bodirsky
Question4.4(see also Question3.2)Definability of co-CSP(B)in k-Datalog is a sufficient condition for tractability of CSP(B),which is sometimes referred to as having width k. There is a game-theoretic characterisation of definability in k-Datalog in terms of(∃,k)-pebble games(see talk by Phokion Kolaitis).
•Is there an algorithm to decide for a given structure B whether co-CSP(B)is definable in k-Datalog(for afixed k)?
•Is the width hierarchy strict?The same question when B isω-categorical,but not necessarilyfinite?
Communicated by:Phokion Kolaitis,Manuel Bodirsky
Question4.5Find a good logic to capture CSP with“nice”(e.g.,ω-categorical)infinite templates.
Communicated by:Iain Stewart 5Graph Theory
Question5.1The list homomorphism problem for a(directed)graph H is equivalent to the problem CSP(H∗)where H∗equals H together with all unary relations.
•It is conjectured that the list homomorphism problem for a reflexive digraph is tractable if H has the X-underbar property(which is the same as having the bi-nary polymorphism some total ordering on the set of vertices),and NP-complete otherwise.
•It is conjectured that the list homomorphism problem for an irreflexive digraph is tractable if H is preserved by a majority operation,and NP-complete otherwise. Do these conjectures hold?
Communicated by:Tomas Feder&Pavol Hell
5

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。