FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 |

«Abstract. The general intractability of the constraint satisfaction prob- lem (CSP) has motivated the study of the complexity of restricted cases of ...»

-- [ Page 1 ] --

Constraint Satisfaction with Succinctly Specified


Hubie Chen and Martin Grohe


Departament de Tecnologia

Universitat Pompeu Fabra

Barcelona, Spain



Institut f¨r Informatik


Humboldt-Universit¨t Berlin


Unter den Linden 6, D-10099 Berlin, Germany


Abstract. The general intractability of the constraint satisfaction prob-

lem (CSP) has motivated the study of the complexity of restricted cases

of this problem. Thus far, the literature has primarily considered the for- mulation of the CSP where constraint relations are given explicitly. We initiate the systematic study of CSP complexity with succinctly specified constraint relations.

1. Introduction Constraint satisfaction problems give a uniform framework for a large number of algorithmic problems in many different areas of computer science, for example, artificial intelligence, database systems, or programming languages. While in- tractable in general, many restricted constraint satisfaction problems are known to be efficiently solvable. Considerable effort went into analysing the precise con- ditions that lead to tractable problems; recent results include [2, 8, 3, 16, 7, 6, 1, 5, 17].

An instance of a constraint satisfaction problem (CSP) is a triple (V, D, C) consisting of a set V of variables, a domain D, and a set C of constraints. The objective is to find an assignment to the variables, of values from D, such that all constraints in C are satisfied. The constraints are expressions of the form Rx1... xk, where R is a k-ary relation on D and x1,..., xk are variables. A constraint is satisfied if the k-tuple of values assigned to the variables x1,..., xk belongs to the relation R. As a running example for this introduction, let us view SAT, the satisfiability problem for CNF-formulas, as a constraint satisfaction over the domain {0, 1}. Constraints are given by the clauses of the input formula.

For example, the clause (x∨¬y∨¬z) corresponds to a constraint Rxyz, where R is the ternary relation {(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)} on the domain {0, 1}.

Two types of restriction on CSP-instances are commonly studied in the lit- erature: restrictions of the constraint language and structural restrictions. The Dagstuhl Seminar Proceedings 06401 Complexity of Constraints http://drops.dagstuhl.de/opus/volltexte/2006/802 former restrict the relations on the domain that are permitted in the constraints.

For example, HORN-SAT is the restriction of SAT where all constraint relations are specified by Horn clauses, that is, clauses with at most one negative literal.

It is known that HORN-SAT can be solved in polynomial time. SAT itself has a restricted constraint language where all constraint relations are specified by disjunctions of literals. The main open problem is the dichotomy conjecture by Feder and Vardi [11], which states that for each constraint language the restricted CSP is either in polynomial time or NP-complete. Currently, this problem still seems to be wide open.

Structural restrictions on CSP-instances are restrictions on the structure induced by the constraints on the variables. A well-known example is the restriction to instances of bounded tree-width. Here a graph on the variables is defined by letting two variables be adjacent if they occur together in some constraint. It is known that for every k the restriction of the general CSP to instances where this graph has tree width at most k, is in polynomial time [10, 13]. The complexity of structural restrictions is better understood than that of constraint language restrictions. If the maximum arity of the constraint relations is bounded, a complete complexity theoretic classification is known [16]; we will state it later in this paper. If the arity is unbounded, interesting classes of tractable problems are known [15, 14, 6, 1, 5, 17], but no complete complexity classification is.

In this paper, we study both restrictions of the constraint language and structural restrictions. We focus on the case of constraint relations of unbounded arity. What is new here is that we pay attention to the way the constraint relations are specified in the problem instances.

In the complexity-theoretic investigations of constraint satisfaction problems it is usually assumed that the constraint relations occurring in a CSP-instance are specified simply by listing all the tuples in the relation, as we did above for the relation specified by the clause (x ∨ ¬y ∨ ¬z). We call this the explicit representation. In practice, the constraint relations are often represented implicitly.

For example, in SAT-instances, the clauses and not the relations they represent are given. Obviously, the implicit clausal representation is exponentially more succinct than the explicit representation, and this may affect the complexity. As long as the arity of the constraint relations is bounded a priori, as in 3-SAT, it does not make much of difference, because the size of the explicit and any implicit representations differ only in a polynomial factor in terms of the overall instance size. If the domain is fixed, they even differ only by a constant factor.

However, for CSPs of unbounded arity, it can make a big difference. What this means in the complexity theoretic context is that algorithms whose running time is polynomial in the size of the explicitly represented instances may become exponential if the instances are represented implicitly. In particular, this is the case for all recent algorithms that exploit a structural restriction called bounded hypertree width and related restrictions [6, 1, 5, 17]. Indeed, these algorithms have been criticised for precisely the reason that they are only polynomial relative to the explicit representation, which is perceived as unrealistic by some researchers.

While we do not share this criticism in general, we agree that there are many 2 examples of CSPs where implicit representations are more natural, such as SAT and systems of equalities or inequalities over some numerical domain. This paper initiates a systematic study of the complexity of CSPs with succinctly specified constraint relations.

Before we can state our main results, we have to get a bit more technical.

1.1. Succinctly specified constraint relations. How can we specify constraints implicitly, and how does this affect the complexity of the CSPs? It will be convenient to consider the Boolean domain {0, 1} first. An abstract implicit representation is to not specify the constraint relations at all, but just assume a membership oracle for each relation. That is, an algorithm may ask if a specific tuple of values belongs to the relation and get an answer in the next step. However, this may lead to CSPs being highly intractable just because their constraint relations are. Consider the family of CSP-instances In := ({v1,..., vn }, {0, 1}, {Rn v1... vn }). To solve such instances, the best an algorithm that knows nothing about Rn and only has access to a membership oracle can do is enumerate all tuples in {0, 1}n and query the oracle for each of them. Thus the running time will be exponential in the worst case, even though the instances In, having just one constraint, are very simple. This type of complexity is clearly not what we are interested in here. Therefore, specifying the constraint relations by membership oracles is “too implicit”; our implicit representation has to be a bit more explicit. A natural and somewhat generic representation of constraint relations over the Boolean domain is by Boolean circuits.

Now consider the family of instances IC := ({v1,..., vn }, {0, 1}, {RC v1... vn }), where RC is the n-ary relation specified by the Boolean circuit C with n inputs.

Again, this is a family of very simple instances with just one constraint. However, solving the instances in this family amounts to solving the Boolean satisfiability problem, which is NP-complete. Therefore, it seems reasonable that an implicit representation has a tractable nonemptiness problem. (The nonemptiness problem for relations specified by circuits is the circuit satisfiability problem.) This not only rules out the representation by arbitrary Boolean circuits, but actually the representation by every class of circuits that contains all CNF-formulas.

Thus, in some sense, the generic representation not ruled out by these considerations is the representation by DNF-formulas. This is the representation we shall study on this paper. Of course there are other natural representations that deserve further study, for example, the representation of the constraint relations by ordered binary decision diagrams, but we defer this to future work.

The DNF representation of constraint relations on the Boolean domain has a natural generalisation to arbitrary domains D: We say that a generalised DNF (GDNF) representation of a relation R ⊆ Dk is an expression of the form m (Pi1 × · · · × Pik ) () i=1 where Pij ⊆ D for 1 ≤ i ≤ m, 1 ≤ j ≤ k. Note that the GDNF enables us to represent relations of size Ω(Dk ) by expressions of size O(m · |D| · k). As the GDNF-representation is the only succinct representation that we study in this 3 paper, from now on we refer to CSPs with constraint relations represented in GDNF as succinctly represented CSPs (sCSPs).

Related previous work has studied restrictions on the SAT problem that lead to tractability [19], which in this discussion corresponds to the case where the domain is boolean and the constraint relations are simply given as a disjunction of literals. In contrast, this paper studies a more general representation and does not impose any size restrictions, other than finiteness, on the domain.

1.2. Main Results. We study the complexity of both structural and constraint language restrictions of succinctly represented CSPs.

We give a complete complexity theoretic classification for structural restriction, which generalises the classification for the bounded arity case obtained in [16]. A structural restriction can be described by a class A of relational structures; we denote the corresponding restricted succinctly represented CSP by sCSP(A, −). We prove that, under the complexity theoretic assumption FPT = W[1], that sCSP(A, −) is in polynomial time if and only if the structures in A are homomorphically equivalent to structures whose incidence graph has bounded tree width (Theorem 8). We refer to this condition by saying that the class A has bounded incidence width modulo homomorphic equivalence.

Constraint language restrictions can also be described by a class B of structures, and we denote them by sCSP(−, B). We prove that two general tractability results can be generalised from the explicitly represented to succinctly represented CSPs. These results are formulated in the algebraic language of polymorphisms of the constraint language. We prove that sCSP(−, B) is in polynomial time if B is a class of relational structures having a near unanimity polymorphism (Theorem 12), or if B is a class of relational structures invariant under a set function (Theorem 13); the corresponding results for explicitly represented constraint relations are from [18, 9].

2. Preliminaries, Definitions, and Basic Facts We use [n] to denote the set containing the first n positive integers, {1,..., n}.

2.1. Relational structures and homomorphisms. As observed by Feder and Vardi [11], constraint satisfaction problems may be viewed as homomorphism problems for relational structures. For the rest of this paper, it will be convenient for us to take this point of view. We review the relevant definitions.

A relational signature is a finite set of relation symbols, each of which has an associated arity. A relational structure A (over signature σ, for short: σ-structure) consists of a universe A and a relation RA over A for each relation symbol R (of σ), such that the arity of RA matches the arity associated to R. When A is a σ-structure and R ∈ σ, the elements of RA are called A-tuples. Throughout this paper, we assume that all relational structures under discussion are finite, that is, have a finite universe. We use boldface letters A, B,... to denote relational structures, and the corresponding non-boldface letters A, B,... to denote their universes. The arity of a vocabulary σ is the maximum of the arities of the relation symbols in σ, and the arity of a relational structure is the arity of its 4 vocabulary. A class A of relational structures has bounded arity if there is a k such that every structure in A has arity at most k.

A substructure of a relational structure A is a relational structure B over the same signature σ as A where B ⊆ A and RB ⊆ RA for all R ∈ σ. A homomorphism from a relational structure A to another relational structure B is a mapping h from the universe of A to the universe of B such that for every relation symbol R and every tuple (a1,..., ak ) ∈ RA, it holds that (h(a1 ),..., h(ak )) ∈ RB. (Here, k denotes the arity of R.)

2.2. Explicitly and Succinctly Represented Constraint Satisfaction Problems. With each CSP-instance I = (V, D, C) we associate two relational structures AI and BI as follows: The signature σI of AI and BI consists of a k-ary relation symbol R for each k-ary constraint relation RI ⊆ Dk of I. The universe of BI is D, and for each relation symbol R ∈ σI we let RB = RI. The universe of AI is V, for each k-ary relation symbol R ∈ σI we let RA = {(x1,..., xk ) | Rx1... xk ∈ C}. Then a mapping f from V = AI to D = BI is a satisfying assignment for I if and only if it is a homomorphism from AI to BI. Thus instance I is satisfiable if and only if there is a homomorphism from AI to BI. Conversely, with every pair (A, B) of σ-structures we can associate a CSP-instance I such that A = AI and B = BI. From now on, we will view CSP-instances as pairs (A, B) of relational structures of the same signature. For succinctly represented instances, the relations of the structure B are represented in GDNF.

Pages:   || 2 | 3 |

Similar works:

«Lubliniec 2020 + Prognoza oddziaływania na środowisko Lokalnego Programu Rewitalizacji Gminy Lubliniec na lata 2014-2020 z perspektywą do 2022 r. Lubliniec – Cieszyn 2015 r. Prognoza Oddziaływania na Środowisko Lokalnego Programu Rewitalizacji Gminy Lubliniec Opracowanie: Stowarzyszenie Wspierania Inicjatyw Gospodarczych DELTA PARTNER Urząd Miejski Lubliniec Autor opracowania: Maciej Majer „4eco” Projektowanie w Ochronie Środowiska 2 Prognoza Oddziaływania na Środowisko Lokalnego...»

«HULU AND THE FUTURE OF TELEVISION: A CASE STUDY An Honors Thesis (HONRS 499) by Matthew Rodgers Thesis Advisor Michael Hanley Associate Professor of Journalism Ball State University Muncie, Indiana May 2011 Expected Date of Graduation May 2011 Abstract Understanding current media trends and adapting to ever-changing consumer desires is essential to success in advertising. Hulu is one of several new Internet-based services that deliver television content to consumers without using the...»

«Facilitating fun and effective meetings Good facilitation makes meetings more useful and more enjoyable for everyone there, and helps groups become more effective. The facilitator serves the group, helping them to keep to agreed meeting processes and attempting to maximise the democracy and inclusivity of those processes. This handout sets out some key facilitation roles and responsibilities, then lists a series of practical tools you and your group may find useful in fulfilling these roles....»

«GENERAL HOUSE RULES 4.1 Operating Days / Hours The Club will be open 7 days a week according to the specified facility listed in this handbook. 4.2 Rules 1. Members should be present at all times when presenting membership cards and signing.2. All Membership cards are non-transferable. Principal members and their dependents must carry with them their Membership Cards at all times. The Club will not carry out services without the presence of a valid membership card. 3. Members are requested to...»

«ANALYSIS OF CODE SWITCHING AND CODE MIXING IN THE TEENLIT CANTING CANTIQ BY DYAN NURANINDYA A THESIS In Partial Fulfillment of the Requirements For the S1 Degree at the English Department Submitted by: DIAS ASTUTI CAKRAWARTI NIM. A2B006028 FACULTY OF HUMANITIES DIPONEGORO UNIVERSITY SEMARANG 2011 PRONOUNCEMENT The writer states truthfully that this thesis is compiled by her without taking the result from other researches in any universities, both in S1 degree or in Diploma degree. Besides, the...»

«State of Tennessee Division of Claims Administration 502 Deaderick Street w Nashville, Tennessee 37243-0202 Teléfono: (615) 741-2734 w Fax: (615) 532-4979 Sitio web: www.treasury.tn.gov/injury Correo Electrónico: Criminal.Injury@tn.gov Una División del Departamento de Tesorería de Tennessee SOLICITUD PARA COMPENSACIÓN POR LESIONES DEBIDAS A UN DELITO EN TENNESSEE PROPÓSITO Cuando una persona resulta lesionada por un delito en el estado de Tennessee, esa víctima o ciertos miembros de su...»

«ABSTRACT Title of Thesis: COMPUTATIONAL ANALYSIS OF THE CONVERSATIONAL DYNAMICS OF THE UNITED STATES SUPREME COURT Timothy W. Hawes, Master of Arts, 2009 Thesis directed by: Professor Jimmy Lin The iSchool Professor Philip Resnik Department of Linguistics The decisions of the United States Supreme Court have far-reaching implications in American life. Using transcripts of Supreme Court oral arguments this work looks at the conversational dynamics of Supreme Court justices and links their...»

«Greyhound Friends for Life Newsline June 2016 GFFL Reunion Marked your calendars for the 2016 GFFL Reunion!Inside This Issue: Sunday, October 2nd 11am – 3pm 1 GFFL Reunion Miller-Knox Regional Park in Point Richmond 1 Tucson Closing Stay tuned for more information in August. 2 Do’s & Don’ts 3 Greyt Info Buddies 4 Sit! Tucson Track Closing 5 Companion Dogs 6 2018 Calendar Many of you have seen the news that Governor Doug Ducey has signed a bill to ban dog racing in the state of Arizona. As...»

«7-15-2015 Judge Shaffer called the regular Gilliam County Court meeting to order at 10:00 a.m. The meeting was held at the Gilliam County Courthouse in Condon, OR. Present were Judge Steve Shaffer, Commissioner Mike Weimar and Commissioner Dennis Gronquist. Absent: None.IN THE MATTER OF FIBER OPTIC DISCUSSION Robert Waltenburg, Co-Superintendent of the North Central Education Service District (NCESD) was present to discuss current and future internet service for the schools in Gilliam County....»

«García Lorca, Transfigured Bodies and the Desire for Reintegration The Spanish poet and playwright, Federico García Lorca, frequently denied that his work was Surrealist.1 Yet, Lorca maintained for many years a close friendship and artistic relationship with Salvador Dalí and Luis Buñuel, Spanish artists who actively associated themselves with the Surrealist movement. Their association led to a certain degree of common imagery, such as an obsession with mutilated and dismembered bodies,...»

«Dominance Solvable Games Felix Munoz-Garcia EconS 424 Strategy and Game Theory Washington State University Solution Concepts The.rst solution concept we will introduce is that of deleting dominated strategies. Intuitively, we seek to delete from the set of strategies o¤ every players those strategies that can never be bene.cial for him regardless of the strategies selected by his opponents. Lets apply this solution concept to the standard prisoner’s dilemma game and then we will de.ne it...»

«AMERICAN STUDIES Vol. XXII Mirosława Buchholtz The American Scene between Fact and Fiction: A Forgotten Book and a Non−Existent Film This film has never been made and thus the present essay speculates about a possibility rather than a cultural fact; the possibility of a documentary based on The American Scene (1907) and following the trajectory of Henry James’s sentimental journey to the United States in 1904 and 1905. Recent trends in the reception of his works in the English−speaking...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.