COMPLEXITY&APPROXIMABILITY OF QUANTIFIED&STOCHASTIC CONSTRAINT SATISFACTION PROBLEMS Page: 3 of 15
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to Digital Library by the UNT Libraries Government Documents Department.
The following text was automatically extracted from the image on this page using optical character recognition software:
Key words: NP-hardness, Approximation Algorithms, PSPACE-hardness,
Quantified and Stochastic Constraint Satisfaction Problems.
1 Introduction and motivation
Over the past thirty years, researchers in theoretical computer science, Al, op-
erations research, and computational algebra have studied versions/variants
of CNF satisfiability, constraint satisfaction problems, and algebraic satisfia-
bility problems (i.e. the problems SAT(F) where F is an algebraic structure).
Two important reasons for the extensive research are the following:
A. Versions/variants of these problems are widely applicable in modeling
both real-life and abstract mathematical problems.
B. These problems, especially versions/variants of the problem 3SAT and Q-
3SAT, have played fundamental roles in the development of discrete complex-
ity theory, providing prototypical complete problems for various complexity
The results, concepts, and techniques reported here are relevant to the
following topical areas of this ongoing research:
1. the complexity of 3SAT and more generally Boolean constraint satisfaction
problems, e.g. [Sc78,GJ79,FV93,JCG97,CJ+00]
2. the development of dichotomy type results for decision and op-
timization versions of Boolean constraint satisfaction problems, e.g.
3. the complexity and (non)-approximability of , PSPACE-hard
quantified and stochastic Boolean satisfiability problems, e.g.,
4. the complexity of decision and optimization problems, when instances are
succinctly specified, e.g. [Le83,LW92,Or82,MH+94], and
5. the complexity of solving systems of equations on various algebraic
structures, e.g. [AC+98,Le83,GJ79,IM83,LW87,AB88,HSM01b].
Here combining these lines of research we study the complexity and efficient
approximability of quantified and stochastic constraint satisfaction problems.
The research program also spans complexity and approximability of solving
quantified and stochastically quantified systems of equations on various alge-
braic structures - due to space limitations we will not discuss these topics in
detail. We recall preliminary definitions that will be helpful in understand-
1 Some of the work done while the author was visiting the Basic and Applied Sim-
ulation Sciences Group at the Los Alamos National Laboratory. supported by the
Department of Energy under Contract W-7405-ENG-36. Also partially supported
by NSF Grant CCR94-06611.
2 Supported by Department of Energy under Contract W-7405-ENG-36.
3 Research supported in part by NSF Grant CCR94-06611.
Here’s what’s next.
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Hunt, H. B. (Harry B.); Marathe, M. V. (Madhav V.) & Stearns, R. E. (Richard E.). COMPLEXITY&APPROXIMABILITY OF QUANTIFIED&STOCHASTIC CONSTRAINT SATISFACTION PROBLEMS, article, January 1, 2001; United States. (digital.library.unt.edu/ark:/67531/metadc933265/m1/3/: accessed December 13, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT Libraries Government Documents Department.