Search results for "computational complexity"
showing 10 items of 249 documents
The computational complexity of the criticality problems in a network with interval activity times
2002
Abstract The paper analyzes the criticality in a network with interval activities duration times. A natural generalization of the criticality notion (for a path, an activity and an event) for the case of network with interval activity duration times is given. The computation complexity of five problems linked to the introduced criticality notion is presented.
Quantum Finite Automata and Logics
2006
The connection between measure once quantum finite automata (MO-QFA) and logic is studied in this paper. The language class recognized by MO-QFA is compared to languages described by the first order logics and modular logics. And the equivalence between languages accepted by MO-QFA and languages described by formulas using Lindstrom quantifier is shown.
Balls into non-uniform bins
2014
Balls-into-bins games for uniform bins are widely used to model randomized load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. These new models are motivated by properties of many peer-to-peer (P2P) networks, which are not able to perfectly balance the load over the bins. While previous evaluations try to find strategies for uniform bins under non-uniform bin selection probabilities, this paper investigates heterogeneous bins, where the "capacities" of the bins might differ significantly. We show that heterogeneous environments can even help to distribute the load more eve…
A multilinear Phelps' Lemma
2007
We prove a multilinear version of Phelps' Lemma: if the zero sets of multilinear forms of norm one are 'close', then so are the multilinear forms.
A Logical Characterisation of Linear Time on Nondeterministic Turing Machines
1999
The paper gives a logical characterisation of the class NTIME(n) of problems that can be solved on a nondeterministic Turing machine in linear time. It is shown that a set L of strings is in this class if and only if there is a formula of the form ∃f1..∃fk∃R1..∃Rm∀xφv; that is true exactly for all strings in L. In this formula the fi are unary function symbols, the Ri are unary relation symbols and φv; is a quantifierfree formula. Furthermore, the quantification of functions is restricted to non-crossing, decreasing functions and in φv; no equations in which different functions occur are allowed. There are a number of variations of this statement, e.g., it holds also for k = 3. From these r…
On the Class of Languages Recognizable by 1-Way Quantum Finite Automata
2007
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.
Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages
2011
We study the recognition of R-trivial idempotent (R1) languages by various models of "decide-and-halt" quantum finite automata (QFA) and probabilistic reversible automata (DH-PRA). We introduce bistochastic QFA (MM-BQFA), a model which generalizes both Nayak's enhanced QFA and DH-PRA. We apply tools from algebraic automata theory and systems of linear inequalities to give a complete characterization of R1 languages recognized by all these models. We also find that "forbidden constructions" known so far do not include all of the languages that cannot be recognized by measure-many QFA.
Postselection Finite Quantum Automata
2010
Postselection for quantum computing devices was introduced by S. Aaronson[2] as an excitingly efficient tool to solve long standing problems of computational complexity related to classical computing devices only. This was a surprising usage of notions of quantum computation. We introduce Aaronson's type postselection in quantum finite automata. There are several nonequivalent definitions of quantumfinite automata. Nearly all of them recognize only regular languages but not all regular languages. We prove that PALINDROMES can be recognized by MM-quantum finite automata with postselection. At first we prove by a direct construction that the complement of this language can be recognized this …
Error-Free Affine, Unitary, and Probabilistic OBDDs
2018
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata versions of these models.
Improved constructions of quantum automata
2008
We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use \frac{4}{\epsilon} \log 2p + O(1) states to recognize a language that requires p states classically. The construction is both substantially simpler and achieves a better constant in the front of \log p than the previously known construction of Ambainis and Freivalds (quant-ph/9802062). Similarly to Ambainis and Freivalds, our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some results in this direction.