This paper gives a brief survey of current research on the complexity of the constraint satisfaction problem over fixed constraint languages.

We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is (...) equivalent to the problem of finding an infinite path through finitely branching recursive trees or recursive binary trees. There are a large number of results in the literature on the complexity of the problem of finding an infinite path through a recursive tree. Our main result allows us to automatically transfer such results to give equivalent results about the complexity of the problem of finding a solution to a recursive constraint satisfaction problem. (shrink)

There exist two conjectures for constraint satisfaction problems of reducts of finitely bounded homogeneous structures: the first one states that tractability of the CSP of such a structure is, when the structure is a model-complete core, equivalent to its polymorphism clone satisfying a certain nontrivial linear identity modulo outer embeddings. The second conjecture, challenging the approach via model-complete cores by reflections, states that tractability is equivalent to the linear identities satisfied by its polymorphisms clone, together with the (...) natural uniformity on it, being nontrivial. We prove that the identities satisfied in the polymorphism clone of a structure allow for conclusions about the orbit growth of its automorphism group, and apply this to show that the two conjectures are equivalent. We contrast this with a counterexample showing that [Formula: see text]-categoricity alone is insufficient to imply the equivalence of the two conditions above in a model-complete core. Taking another approach, we then show how the Ramsey property of a homogeneous structure can be utilized for obtaining a similar equivalence under different conditions. We then prove that any polymorphism of sufficiently large arity which is totally symmetric modulo outer embeddings of a finitely bounded structure can be turned into a nontrivial system of linear identities, and obtain nontrivial linear identities for all tractable cases of reducts of the rational order, the random graph, and the random poset. Finally, we provide a new and short proof, in the language of monoids, of the theorem stating that every [Formula: see text]-categorical structure is homomorphically equivalent to a model-complete core. (shrink)

Journal of Mathematical Logic, Ahead of Print.

We observe a number of connections between recent developments in the study of constraint satisfaction problems, irredundant axiomatisation and the study of topological quasivarieties. Several restricted forms of a conjecture of Clark, Davey, Jackson and Pitkethly are solved: for example we show that if, for a finite relational structure M, the class of M-colourable structures has no finite axiomatisation in first order logic, then there is no set (even infinite) of first order sentences characterising the continuously M-colourable (...) structures amongst compact totally disconnected relational structures. We also refute a rather old conjecture of Gorbunov by presenting a finite structure with an infinite irredundant quasi-identity basis. (shrink)

This paper provides a computational characterization of coherence that applies to a wide range of philosophical problems and psychological phenomena. Maximizing coherence is a matter of maximizing satisfaction of a set of positive and negative constraints. After comparing five algorithms for maximizing coherence, we show how our characterization of coherence overcomes traditional philosophical objections about circularity and truth.

In Wason’s Selection Task, subjects: process information from the instructions and build a mental representation of the problem, then: select a course of action to solve the problem,under the constraints imposed by the instructions. We analyze both aspects as part of a constraint satisfaction problem without assuming Wason’s ‘logical’ solution to be the correct one. We show that outcome of step may induce mutually inconsistent constraints, causing subjects to select at step solutions that violate some of them. Our (...) analysis explains why inconsistent constraints are less likely disrupt non-abstract versions of the tasks, but unlike Bayesians does not posit different mechanisms in abstract and thematic variants. We then assess the logicality of the task, and conclude on cognitive tasks as coordination problems. (shrink)

In a seminal 1977 article, Rumelhart argued that perception required the simultaneous use of multiple sources of information, allowing perceivers to optimally interpret sensory information at many levels of representation in real time as information arrives. Building on Rumelhart's arguments, we present the Interactive Activation hypothesis—the idea that the mechanism used in perception and comprehension to achieve these feats exploits an interactive activation process implemented through the bidirectional propagation of activation among simple processing units. We then examine the interactive activation (...) model of letter and word perception and the TRACE model of speech perception, as early attempts to explore this hypothesis, and review the experimental evidence relevant to their assumptions and predictions. We consider how well these models address the computational challenge posed by the problem of perception, and we consider how consistent they are with evidence from behavioral experiments. We examine empirical and theoretical controversies surrounding the idea of interactive processing, including a controversy that swirls around the relationship between interactive computation and optimal Bayesian inference. Some of the implementation details of early versions of interactive activation models caused deviation from optimality and from aspects of human performance data. More recent versions of these models, however, overcome these deficiencies. Among these is a model called the multinomial interactive activation model, which explicitly links interactive activation and Bayesian computations. We also review evidence from neurophysiological and neuroimaging studies supporting the view that interactive processing is a characteristic of the perceptual processing machinery in the brain. In sum, we argue that a computational analysis, as well as behavioral and neuroscience evidence, all support the Interactive Activation hypothesis. The evidence suggests that contemporary versions of models based on the idea of interactive activation continue to provide a basis for efforts to achieve a fuller understanding of the process of perception. (shrink)

Motivated by constraint satisfaction problems, Feder and Vardi (SIAM Journal of Computing, 28, 57–104, 1998) set out to search for fragments of satisfying the dichotomy property: every problem definable in is either in P or else NP-complete. Feder and Vardi considered in this connection two logics, strict NP (or SNP) and monadic, monotone, strict NP without inequalities (or MMSNP). The former consists of formulas of the form , where is a quantifier-free formula in a relational vocabulary; and (...) the latter is the fragment of SNP whose formulas involve only negative occurrences of relation symbols, only monadic second-order quantifiers, and no occurrences of the equality symbol. It remains an open problem whether MMSNP enjoys the dichotomy property. In the present paper, SNP and MMSNP are characterized in terms of partially ordered connectives. More specifically, SNP is characterized using the logic D of partially ordered connectives introduced in Blass and Gurevich (Annals of Pure and Applied Logic, 32, 1–16, 1986), Sandu and Väänänen (Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 38, 361–372 1992), and MMSNP employing a generalization C of D introduced in the present paper. (shrink)

The field service scheduling problem is the key problem in field services. Field service pays particular attention to customer experience, that is, customer satisfaction. Customer satisfaction described by customer behavior characteristics based on the prospect theory is considered as the primary optimization goal in this paper. The knowledge of the insertion feasibility on the solution is analysed based on the skill constraint and time window. According to the knowledge, an initialization method based on the nearest heuristic algorithm (...) is constructed. Based on the prior knowledge of the FSSP and the endowment of the Fruit Fly Optimization Algorithm, two operators are defined according to the matrix encoding method. Based on these two operators, three search strategies are then proposed, and the smell-based search strategy and vision-based search strategy for the FOA are redesigned. To verify the performance of the algorithms, the proposed operators and strategies are tested and analysed in the well-known benchmark. Through comparison with the state-of-the-art algorithms, the results show that the proposed HFOA is an effective and efficient method to solve the FSSP with customer satisfaction. (shrink)

Model RB is a model of random constraint satisfaction problems, which exhibits exact satisfiability phase transition and many hard instances, both experimentally and theoretically. Benchmarks based on Model RB have been successfully used by various international algorithm competitions and many research papers. In a previous work, Xu and Li defined two notions called i-constraint assignment tuple and flawed i-constraint assignment tuple to show an exponential resolution complexity of Model RB. These two notions are similar to (...) some kind of consistency in constraint satisfaction problems, but seem different from all kinds of consistency so far known in literatures. In this paper, we explicitly define this kind of consistency, called variable-centered consistency, and show an upper bound on a parameter in Model RB, such that up to this bound the typical instances of Model RB are variable-centered consistent. (shrink)

Estimation of Distribution Algorithms, which employ probabilistic models to generate the next population, are new promising methods in the field of genetic and evolutionary algorithms. In the case of conventional Genetic and Evolutionary Algorithms are applied to Constraint Satisfaction Problems, it is well-known that the incorporation of the domain knowledge in the Constraint Satisfaction Problems is quite effective. In this paper, we constitute a memetic algorithm as a combination of the Estimation of Distribution Algorithm (...) and a repair method. Experimental results on general Constraint Satisfaction Problems tell us the effectiveness of the proposed method. (shrink)

The aim of this study was to compare the learning effectiveness of peer tutored problem-based learning and conventional teaching of nursing ethics in Taiwan. The study adopted an experimental design. The peer tutored problem-based learning method was applied to an experimental group and the conventional teaching method to a control group. The study sample consisted of 142 senior nursing students who were randomly assigned to the two groups. All the students were tested for their nursing ethical discrimination ability both before (...) and after the educational intervention. A learning satisfaction survey was also administered to both groups at the end of each course. After the intervention, both groups showed a significant increase in ethical discrimination ability. There was a statistically significant difference between the ethical discrimination scores of the two groups (P < 0.05), with the experimental group on average scoring higher than the control group. There were significant differences in satisfaction with self-motivated learning and critical thinking between the groups. Peer tutored problem-based learning and lecture-type conventional teaching were both effective for nursing ethics education, but problem-based learning was shown to be more effective. Peer tutored problem-based learning has the potential to enhance the efficacy of teaching nursing ethics in situations in which there are personnel and resource constraints. (shrink)

Background Moral distress is a complex and challenging issue in the nursing profession that can negatively affect the nurses’ job satisfaction and retention and the quality of patient care. This study focused on describing the resources and constraints, consequences, and interventions of moral distress in nurses. Methods In a literature review, an extensive electronic search was conducted in databases including PubMed, ISI, Scopus as well as Google Scholar search engine using the keywords including “moral distress” and “nurses” to identify (...) resources, constraints, consequences, and interventions about moral distress in nurses, from the earliest records up to 26 December 2020. The required data were extracted from 61 relevant studies by two independent reviewers. Results Resources and constraints in the occurrence of moral distress among nurses can be divided into three general categories including internal factors, clinical factors, and external factors. The consequences of moral distress on nurses and the medical system reduced moral sensitivity, development of psychological and physical health problems, and the intention to leave the profession. The potential effective interventions were the implementation of integrated communication programs, strengthening physician–nurse collaboration, nursing involvement in clinical decision-making and end-of-life issues, social support, using a resiliency bundle, interdisciplinary discussion, and promoting nurses’ ethical and communication skills. Conclusion There are a wide range of resources and constraints impacting moral distress in nurses that could lead to negative consequences. Further studies are necessary to identify, evaluate, and implement a range of potential effective interventions for the management of moral distress in nurses. (shrink)

Many stochastic search algorithms have recently been developed to make more remarkable progress than systematic search algorithms because stochastic algorithms sometimes solve large-scale constraint satisfaction problems in a practical time. However, such stochastic algorithms have the drawback of getting stuck in local optima which are not acceptable as final solutions. We analyze an iterative improvement algorithm from the viewpoint of constraint structures causing local optima. Using the graph-coloring problem with three colors, an archetype problem to evaluate (...) constraint satisfaction algorithms, we study the local graph structures around which so many conflicts thrash. We propose a key constraint structure, an LM pair, which may induce a local optimum, and clarify the mechanism of how conflicting colors for an LM pair obstruct the stepwise refinement of hill-climbing. Experimental results show that LM pairs are strongly correlated with the search efficiency of the stochastic search algorithm. (shrink)