Search results for "Computer Science::Computational Complexity"
showing 8 items of 48 documents
On the class of languages recognizable by 1-way quantum finite automata
2000
It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient. Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.
The class of languages recognizable by 1-way quantum finite automata is not closed under union
2000
In this paper we develop little further the theory of quantum finite automata (QFA). There are already few properties of QFA known, that deterministic and probabilistic finite automata do not have e.g. they cannot recognize all regular languages. In this paper we show, that class of languages recognizable by QFA is not closed under union, even not under any Boolean operation, where both arguments are significant.
Unary Probabilistic and Quantum Automata on Promise Problems
2015
We continue the systematic investigation of probabilistic and quantum finite automata (PFAs and QFAs) on promise problems by focusing on unary languages. We show that bounded-error QFAs are more powerful than PFAs. But, in contrary to the binary problems, the computational powers of Las-Vegas QFAs and bounded-error PFAs are equivalent to deterministic finite automata (DFAs). Lastly, we present a new family of unary promise problems with two parameters such that when fixing one parameter QFAs can be exponentially more succinct than PFAs and when fixing the other parameter PFAs can be exponentially more succinct than DFAs.
Some Computational Aspects of DISTANCE-SAT
2007
In many AI fields, one must face the problem of finding a solution that is as close as possible to a given configuration. This paper addresses this problem in a propositional framework. We introduce the decision problem distance-sat, which consists in determining whether a propositional formula admits a model that disagrees with a given partial interpretation on at most d variables. The complexity of distance-sat and of several restrictions of it are identified. Two algorithms based on the well-known Davis/Logemann/Loveland search procedure for the satisfiability problem sat are presented so as to solve distance-sat for CNF formulas. Their computational behaviors are compared with the ones …
Full CNF Encoding: The Counting Constraints Case
2004
Many problems are naturally expressed using CNF clauses and boolean cardinality constraints. It is generally believed that solving such problems through pure CNF encoding is inefficient, so many authors has proposed specialized algorithms : the pseudo-boolean solvers. In this paper we show that an appropriate pure CNF encoding can be competitive with these specialized methods. In conjunction with our encoding, we propose a slight modification of the DLL procedure that allows any DLL-based SAT solver to solve boolean cardinality optimization problems. We show experimentally that our encoding allows zchaff to be competitive with pseudo-boolean solvers on some decision and optimization problem…
A Translation of Pseudo Boolean Constraints to SAT
2006
Research note; This paper introduces a new CNF encoding of pseudo-Boolean constraints, which allows unit propagation to maintain generalized arc consistency. In the worst case, the size of the produced formula can be exponentially related to the size of the input constraint, but some important classes of pseudo-Boolean constraints, including Boolean cardinality constraints, are encoded in polynomial time and size. The proposed encoding was integrated in a solver based on the zCha SAT solver and submitted to the PB05 evaluation. The results provide new perspectives in the field of full CNF approach of pseudo-Boolean constraints solving.
Varieties Generated by Certain Models of Reversible Finite Automata
2006
Reversible finite automata with halting states (RFA) were first considered by Ambainis and Freivalds to facilitate the research of Kondacs-Watrous quantum finite automata. In this paper we consider some of the algebraic properties of RFA, namely the varieties these automata generate. Consequently, we obtain a characterization of the boolean closure of the classes of languages recognized by these models.
Very narrow quantum OBDDs and width hierarchies for classical OBDDs
2014
In the paper we investigate a model for computing of Boolean functions - Ordered Binary Decision Diagrams (OBDDs), which is a restricted version of Branching Programs. We present several results on the comparative complexity for several variants of OBDD models. - We present some results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2 k+1. - We consider quantum and classical nondeterminism. We show that quantum nondeterminism can be more efficien…