The Experts below are selected from a list of 1032 Experts worldwide ranked by ideXlab platform
Yamakami Tomoyuki - One of the best experts on this subject based on the ideXlab platform.
-
Constant Unary Constraints and Symmetric Real-Weighted Counting Constraint Satisfaction Problems
'Springer Science and Business Media LLC', 2013Co-Authors: Yamakami TomoyukiAbstract:A Unary Constraint (on the Boolean domain) is a function from {0,1} to the set of real numbers. A free use of auxiliary Unary Constraints given besides input instances has proven to be useful in establishing a complete classification of the computational complexity of approximately solving weighted counting Boolean Constraint satisfaction problems (or #CSPs). In particular, two special constant Unary Constraints are a key to an arity reduction of arbitrary Constraints, sufficient for the desired classification. In an exact counting model, both constant Unary Constraints are always assumed to be available since they can be eliminated efficiently using an arbitrary nonempty set of Constraints. In contrast, we demonstrate in an approximate counting model, that at least one of them is efficiently approximated and thus eliminated approximately by a nonempty Constraint set. This fact directly leads to an efficient construction of polynomial-time randomized approximation-preserving Turing reductions (or AP-reductions) from #CSPs with designated Constraints to any given #CSPs composed of symmetric real-valued Constraints of arbitrary arities even in the presence of arbitrary extra Unary Constraints.Comment: 10pt, A4, 21 pages. This is a complete version of the paper (under a slightly concise title) that appeared in the Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC 2012), Taipei, Taiwan, December 19-21, 2012, Lecture Notes in Computer Science, Springer-Verlag, vol.7676, pp.237-246, 201
Pavol Hell - One of the best experts on this subject based on the ideXlab platform.
-
full Constraint satisfaction problems
SIAM Journal on Computing, 2006Co-Authors: Tomas Feder, Pavol HellAbstract:Feder and Vardi have conjectured that all Constraint satisfaction problems to a fixed structure (Constraint language) are polynomial or NP-complete. This so-called dichotomy conjecture remains open, although it has been proved in a number of special cases. Most recently, Bulatov has verified the conjecture for conservative structures, i.e., structures which contain all possible Unary relations. We explore three different implications of Bulatov's result. First, the above dichotomy can be extended to so-called inclusive structures, corresponding to conservative Constraint satisfaction problems in which each variable comes with its own domain. (This has also been independently observed by Bulatov.) We prove a more general version, extending the dichotomy to so-called three-inclusive structures, i.e., structures which contain, with any Unary relation $R$, all Unary relations $R'$ for subsets $R' \subseteq R$ with at most three elements. For the Constraint satisfaction problems in this generalization we must restrict the instances to so-called $1$-full structures, in which each variable is involved in a Unary Constraint. This leads to our second focus, which is on restrictions to more general kinds of "full" input structures. For any set $W$ of positive integers, we consider a restriction to $W$-full input structures, i.e., structures in which, for each $w \in W$, any $w$ variables are involved in a $w$-ary Constraint. We identify a class of structures (the so-called $W$-set-full structures) for which the restriction to $W$-full input structures does not change the complexity of the Constraint satisfaction problem, and hence the family of these restricted problems also exhibits dichotomy. The general family of three-inclusive Constraint satisfaction problems restricted to $W$-full input structures contains examples which we cannot seem to prove either polynomial or NP-complete. Nevertheless, we are able to use our result on the dichotomy for three-inclusive Constraint satisfaction problems, to deduce the fact that all three-inclusive Constraint satisfaction problems restricted to $W$-full input structures are NP-complete or "quasi-polynomial" (of order $n^{O(\log n)}$). Our third focus deals with bounding the number of occurrences of a variable, which we call the degree. We conjecture that the complexity classification of three-inclusive Constraint satisfaction problems extends to the case where all degrees are bounded by three. Using previous results, we are able to verify this conjecture in a number of special cases. Conservative, inclusive, and three-inclusive Constraint satisfaction problems can be viewed as problems in which each variable is restricted to a "list" of allowed values. This point of view of lists is frequently encountered in the study of graph colorings, graph homomorphisms, and graph partitions. Our results presented here, in all three areas, were strongly motivated by these results on graphs.
Tomas Feder - One of the best experts on this subject based on the ideXlab platform.
-
full Constraint satisfaction problems
SIAM Journal on Computing, 2006Co-Authors: Tomas Feder, Pavol HellAbstract:Feder and Vardi have conjectured that all Constraint satisfaction problems to a fixed structure (Constraint language) are polynomial or NP-complete. This so-called dichotomy conjecture remains open, although it has been proved in a number of special cases. Most recently, Bulatov has verified the conjecture for conservative structures, i.e., structures which contain all possible Unary relations. We explore three different implications of Bulatov's result. First, the above dichotomy can be extended to so-called inclusive structures, corresponding to conservative Constraint satisfaction problems in which each variable comes with its own domain. (This has also been independently observed by Bulatov.) We prove a more general version, extending the dichotomy to so-called three-inclusive structures, i.e., structures which contain, with any Unary relation $R$, all Unary relations $R'$ for subsets $R' \subseteq R$ with at most three elements. For the Constraint satisfaction problems in this generalization we must restrict the instances to so-called $1$-full structures, in which each variable is involved in a Unary Constraint. This leads to our second focus, which is on restrictions to more general kinds of "full" input structures. For any set $W$ of positive integers, we consider a restriction to $W$-full input structures, i.e., structures in which, for each $w \in W$, any $w$ variables are involved in a $w$-ary Constraint. We identify a class of structures (the so-called $W$-set-full structures) for which the restriction to $W$-full input structures does not change the complexity of the Constraint satisfaction problem, and hence the family of these restricted problems also exhibits dichotomy. The general family of three-inclusive Constraint satisfaction problems restricted to $W$-full input structures contains examples which we cannot seem to prove either polynomial or NP-complete. Nevertheless, we are able to use our result on the dichotomy for three-inclusive Constraint satisfaction problems, to deduce the fact that all three-inclusive Constraint satisfaction problems restricted to $W$-full input structures are NP-complete or "quasi-polynomial" (of order $n^{O(\log n)}$). Our third focus deals with bounding the number of occurrences of a variable, which we call the degree. We conjecture that the complexity classification of three-inclusive Constraint satisfaction problems extends to the case where all degrees are bounded by three. Using previous results, we are able to verify this conjecture in a number of special cases. Conservative, inclusive, and three-inclusive Constraint satisfaction problems can be viewed as problems in which each variable is restricted to a "list" of allowed values. This point of view of lists is frequently encountered in the study of graph colorings, graph homomorphisms, and graph partitions. Our results presented here, in all three areas, were strongly motivated by these results on graphs.
Guanghui Liu - One of the best experts on this subject based on the ideXlab platform.
-
a new co saliency model via pairwise Constraint graph matching
International Symposium on Intelligent Signal Processing and Communication Systems, 2012Co-Authors: Fanman Meng, Guanghui LiuAbstract:In this paper, we propose a new co-saliency model to extract co-saliency maps from a pair of images. Rather than using Unary Constraint matching, we use pairwise Constraint graph matching to obtain more accurate co-saliency map. In our method, the co-saliency map consists of two terms, i.e., the single image saliency map and the multiple image saliency map. The single image saliency map is obtained by traditional saliency detection method. The multiple image saliency map is extracted by matching the similar regions among the images, which is casted as pairwise Constraint graph matching problem. The dynamic programming method is used to solve the matching problem. We test the proposed co-saliency model on co-saliency dataset. The experimental results demonstrate the effectiveness of the proposed co-saliency model.
John C Mitchell - One of the best experts on this subject based on the ideXlab platform.
-
datalog with Constraints a foundation for trust management languages
Practical Aspects of Declarative Languages, 2003Co-Authors: John C MitchellAbstract:Trust management (TM) is a promising approach for authorization and access control in distributed systems, based on signed distributed policy statements expressed in a policy language. Although several TM languages are semantically equivalent to subsets of Datalog, Datalog is not sufficiently expressive for fine-grained control of structured resources. We define the class of linearly decomposable Unary Constraint domains, prove that DATALOG extended with Constraints in any combination of such Constraint domains is tractable, and show that permissions associated with structured resources fall into this class. We also present a concrete declarative TM language, RT1C, based on Constraint DATALOG, and use Constraint DATALOG to analyze another TM system, KeyNote, which turns out to be less expressive than RT1C in significant respects, yet less tractable in the worst case. Although Constraint DATALOG has been studied in the context of Constraint databases, TM applications involve different kinds of Constraint domains and have different computational complexity requirements.