Regular-SAT: A many-valued approach to solving combinatorial problems

Regular-SAT is a constraint programming language between CSP and SAT that—by combining many of the good properties of each paradigm—offers a good compromise between performance and expressive power. Its similarity to SAT allows us to define a uniform encoding formalism, to extend existing SAT algorithms to Regular-SAT without incurring excessive overhead in terms of computational cost, and to identify phase transition phenomena in randomly generated instances. On the other hand, Regular-SAT inherits from CSP more compact and natural encodings that maintain more the structure of the original problem. Our experimental results—using a range of benchmark problems—provide evidence that Regular-SAT offers practical computational advantages for solving combinatorial problems.     

Weighted o-minimal hybrid systems

We consider weighted o-minimal hybrid systems, which extend classical o-minimal hybrid systems with cost functions. These cost functions are “observer variables” which increase while the system evolves but do not constrain the behaviour of the system. In this paper, we prove two main results: (i) optimal o-minimal hybrid games are decidable; (ii) the model-checking of WCTL, an extension of CTL which can constrain the cost variables, is decidable over that model. This has to be compared with the same problems in the framework of timed automata where both problems are undecidable in general, while they are decidable for the restricted class of one-clock timed automata.     

Abelian-by-G Groups,for G Finite,from the Model Theoretic Point of View

Let G be a finite group. We prove that the theory af abelian-by-G groups is decidable if and only if the theory of modules over the group ring ?[G] is decidable. Then we study some model theoretic questions about abelian-by-G groups, in particular we show that their class is elementary when the order of G is squarefree. Mathematics Subject Classification: 03C60, 03B25.     

二级传递性与二级传递模糊矩阵

推广传递性概念,给出二级传递性的定义;研究二级传递模糊矩阵的性质,给出其若干等价刻画;证明二级传递模糊矩阵或者收敛或者周期为2,指数不大于n 1;讨论二级传递与强传递、k-传递和泛传递等概念之间的关系,指出二级传递是传递性概念的一种新的推广形式。     

The group PSL(2,q) is not the multiplication group of a loop

ABSTRACT

We introduce the notion of weak transitivity for torsion-free abelian groups. A torsion-free abelian group G is called weakly transitive if for any pair of elements x, y ∈ G and endomorphisms ?, ψ ∈ End(G) such that x? = y, yψ = x, there exists an automorphism of G mapping x onto y. It is shown that every suitable ring can be realized as the endomorphism ring of a weakly transitive torsion-free abelian group, and we characterize up to a number-theoretical property the separable weakly transitive torsion-free abelian groups.     

Positivity of third order linear recurrence sequences

It is shown that the Positivity Problem for a sequence satisfying a third order linear recurrence with integer coefficients, i.e., the problem whether each element of this sequence is nonnegative, is decidable.     

Some observations on fuzzy relations over fuzzy subsets

This paper considers fuzzy relations defined over fuzzy subsets and settles some open problems regarding the distributivity and transitivity of such relations     

Dynamics of quasicontinuous systems

Quasicontinuous functions are continuous on a residual subset of their domain. The class includes many standard examples from dynamical systems, including the baker transformation and interval exchange maps. We present standard results of continuous topological dynamics (such as that sensitive dependence follows from transitivity and dense periodic points) which extend to quasicontinuous dynamics     

Semidefinite resolution and exactness of semidefinite relaxations for satisfiability

This paper explores new connections between the satisfiability problem and semidefinite programming. We show how the process of resolution in satisfiability is equivalent to a linear transformation between the feasible sets of the relevant semidefinite programming problems. We call this transformation semidefinite programming resolution, and we demonstrate the potential of this novel concept by using it to obtain a direct proof of the exactness of the semidefinite formulation of satisfiability without applying Lasserre’s general theory for semidefinite relaxations of 0/1 problems. In particular, our proof explicitly shows how the exactness of the semidefinite formulation for any satisfiability formula can be interpreted as the implicit application of a finite sequence of resolution steps to verify whether the empty clause can be derived from the given formula.     

A geometric averaging procedure for constructing supertransitive approximation to binary comparison matrices

The usefulness of encoding the fuzzy evaluations of alternatives and the importance weights of criteria, in a multiple objective decision problem through binary comparison matrices (or pairwise judgment matrices) is receiving considerable attention. The methodology for identifying the best alternative in a given decision problem involves the computation of the principal eigenvectors of the binary comparison matrices. The eigenvectors transform the fuzzy evaluations of the importance of the criteria and the ratings of the alternatives into a ratio scale. A difficulty that is often experienced in using this approach in practice, is the inconsistency of the binary evaluations. This paper proposes a simple averaging procedure to construct a supertransitive approximation to a binary comparison matrix, where inconsistency is a problem. It is further suggested that such an adjustment might be necessary to more closely reflect the inherent fuzziness of the evaluations contained in a binary comparison matrix. The procedure is illustrated by means of examples.     

Phase transitions of PP-complete satisfiability problems

The complexity class PP consists of all decision problems solvable by polynomial-time probabilistic Turing machines. It is well known that PP is a highly intractable complexity class and that PP-complete problems are in all likelihood harder than NP-complete problems. We investigate the existence of phase transitions for a family of PP-complete Boolean satisfiability problems under the fixed clauses-to-variables ratio model. A typical member of this family is the decision problem # 3SAT(?2^n/2): given a 3CNF-formula, is it satisfied by at least the square-root of the total number of possible truth assignments? We provide evidence to the effect that there is a critical ratio r_3,2 at which the asymptotic probability of # 3SAT(?2^n/2) undergoes a phase transition from 1 to 0. We obtain upper and lower bounds for r_3,2 by showing that 0.9227?r_3,2?2.595. We also carry out a set of experiments on random instances of # 3SAT(?2^n/2) using a natural modification of the Davis-Putnam-Logemann-Loveland (DPLL) procedure. Our experimental results suggest that r_3,2≈2.5. Moreover, the average number of recursive calls of this modified DPLL procedure reaches a peak around 2.5 as well.     

Testing satisfiability

Let Φ be a set of general boolean functions on n variables, such that each function depends on exactly k variables, and each variable can take a value from [1,d]. We say that Φ is ε-far from satisfiable, if one must remove at least εn^k functions in order to make the set of remaining functions satisfiable. Our main result is that if Φ is ε-far from satisfiable, then most of the induced sets of functions, on sets of variables of size c(k,d)/ε², are not satisfiable, where c(k,d) depends only on k and d. Using the above claim, we obtain similar results for k-SAT and k-NAEQ-SAT.Assume we relax the decision problem of whether an instance of one of the above mentioned problems is satisfiable or not, to the problem of deciding whether an instance is satisfiable or ε-far from satisfiable. While the above decision problems are NP-hard, our result implies that we can solve their relaxed versions, that is, distinguishing between satisfiable and ε-far from satisfiable instances, in randomized constant time.From the above result we obtain as a special case, previous results of Alon and Krivelevich, and of Czumaj and Sohler, concerning testing of graphs and hypergraphs colorability. We also discuss the difference between testing with one-sided and two-sided error.     

Polar SAT and related graphs

We introduce polar SAT and show that a general SAT can be reduced to it in polynomial time. A set of clauses C is called polar if there exists a partition C^pCⁿ=C, called a polar partition, such that each clause in C^p involves only positive (i.e., non-complemented) variables, while each clause in Cⁿ contains only negative (i.e., complemented) variables. A polar set of clauses C=(C^p,Cⁿ) is called (p,n)-polar, where p1 and n1, if each clause in C^p (respectively, in Cⁿ) contains exactly p (respectively, exactly n) literals. We classify all (p,n)-polar SAT Problems according to their complexity. Specifically, a (p,n)-Polar SAT problem is NP-complete if either p>n2 or n>p2. Otherwise it can be solved in polynomial time. We introduce two new hereditary classes of graphs, namely polar satgraphs and polar (3,2)-satgraphs, and we characterize them in terms of forbidden induced subgraphs. Both characterization involve an infinite number of minimal forbidden induced subgraphs. As are result, we obtain two narrow hereditary subclasses of weakly chordal graphs where Independent Domination is an NP-complete problem.