Search results for "Computational complexity"
showing 10 items of 249 documents
Log-space counter is useful for unary languages by help of a constant-size quantum register
2013
The minimum amount of resources to recognize a nonregular language is a fundamental research topic in theoretical computer science which has been examined for different kinds of resources and many different models. In this note, we focus on unary languages and space complexity on counters. Our model is two-way one-counter automaton with quantum and classical states (2QCCA), which is a two-way finite automaton with one-counter (2DCA) augmented with a fixed size quantum register or a two-way finite automaton with quantum and classical states (2QCFA) augmented with a classical counter. It is known that any 2DCA using a sublinear space on its counter can recognize only regular languages \cite{D…
Quantum versus Classical Online Streaming Algorithms with Logarithmic Size of Memory
2023
We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with non-constant size of memory (streaming algorithms) as a model for online algorithms. We construct problems that can be solved by quantum online streaming algorithms better than by classical ones in a case of logarithmic or sublogarithmic size of memory.
Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
2017
We consider Quantum OBDD model. It is restricted version of read-once Quantum Branching Programs, with respect to "width" complexity. It is known that maximal complexity gap between deterministic and quantum model is exponential. But there are few examples of such functions. We present method (called "reordering"), which allows to build Boolean function $g$ from Boolean Function $f$, such that if for $f$ we have gap between quantum and deterministic OBDD complexity for natural order of variables, then we have almost the same gap for function $g$, but for any order. Using it we construct the total function $REQ$ which deterministic OBDD complexity is $2^{\Omega(n/\log n)}$ and present quantu…
NP has log-space verifiers with fixed-size public quantum registers
2011
In classical Arthur-Merlin games, the class of languages whose membership proofs can be verified by Arthur using logarithmic space (AM(log-space)) coincides with the class P \cite{Co89}. In this note, we show that if Arthur has a fixed-size quantum register (the size of the register does not depend on the length of the input) instead of another source of random bits, membership in any language in NP can be verified with any desired error bound.
One-counter verifiers for decidable languages
2012
Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working memory, i.e. replacing the working tape(s) with a single counter, we can define some IPS's for each decidable language. Such verifiers are called two-way probabilistic one-counter automata (2pca's). Then, we show that by adding a fixed-size quantum memory to a 2pca, called a two-way one-counter automaton with quantum and classical states (2qcca), the protocol can be spac…
New Results on the Minimum Amount of Useful Space
2014
We present several new results on minimal space requirements to recognize a nonregular language: (i) realtime nondeterministic Turing machines can recognize a nonregular unary language within weak $\log\log n$ space, (ii) $\log\log n$ is a tight space lower bound for accepting general nonregular languages on weak realtime pushdown automata, (iii) there exist unary nonregular languages accepted by realtime alternating one-counter automata within weak $\log n$ space, (iv) there exist nonregular languages accepted by two-way deterministic pushdown automata within strong $\log\log n$ space, and, (v) there exist unary nonregular languages accepted by two-way one-counter automata using quantum an…
Weak Parity
2013
We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2 + ε fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that n randomized queries and n/2 quantum queries are needed to compute parity on all inputs. But surprisingly, we give a randomized algorithm for Weak Parity that makes only O(n/log[superscript 0.246](1/ε)) queries, as well as a quantum algorithm that makes O(n/√log(1/ε)) queries. We also prove a lower bound of Ω(n/log(1/ε)) in both cases, as well as lower bounds of Ω(logn) in the randomized case and Ω(√logn) in the quantu…
New results on classical and quantum counter automata
2019
We show that one-way quantum one-counter automaton with zero-error is more powerful than its probabilistic counterpart on promise problems. Then, we obtain a similar separation result between Las Vegas one-way probabilistic one-counter automaton and one-way deterministic one-counter automaton. We also obtain new results on classical counter automata regarding language recognition. It was conjectured that one-way probabilistic one blind-counter automata cannot recognize Kleene closure of equality language [A. Yakaryilmaz: Superiority of one-way and realtime quantum machines. RAIRO - Theor. Inf. and Applic. 46(4): 615-641 (2012)]. We show that this conjecture is false, and also show several s…
Real-Time Vector Automata
2013
We study the computational power of real-time finite automata that have been augmented with a vector of dimension k, and programmed to multiply this vector at each step by an appropriately selected $k \times k$ matrix. Only one entry of the vector can be tested for equality to 1 at any time. Classes of languages recognized by deterministic, nondeterministic, and "blind" versions of these machines are studied and compared with each other, and the associated classes for multicounter automata, automata with multiplication, and generalized finite automata.
Postselecting probabilistic finite state recognizers and verifiers
2018
In this paper, we investigate the computational and verification power of bounded-error postselecting realtime probabilistic finite state automata (PostPFAs). We show that PostPFAs using rational-valued transitions can do different variants of equality checks and they can verify some nonregular unary languages. Then, we allow them to use real-valued transitions (magic-coins) and show that they can recognize uncountably many binary languages by help of a counter and verify uncountably many unary languages by help of a prover. We also present some corollaries on probabilistic counter automata.