Search results for " Complexity theory"
showing 10 items of 131 documents
Algorithmic Information Theory and Computational Complexity
2013
We present examples where theorems on complexity of computation are proved using methods in algorithmic information theory. The first example is a non-effective construction of a language for which the size of any deterministic finite automaton exceeds the size of a probabilistic finite automaton with a bounded error exponentially. The second example refers to frequency computation. Frequency computation was introduced by Rose and McNaughton in early sixties and developed by Trakhtenbrot, Kinber, Degtev, Wechsung, Hinrichs and others. A transducer is a finite-state automaton with an input and an output. We consider the possibilities of probabilistic and frequency transducers and prove sever…
Transition Function Complexity of Finite Automata
2011
State complexity of finite automata in some cases gives the same complexity value for automata which intuitively seem to have completely different complexities. In this paper we consider a new measure of descriptional complexity of finite automata -- BC-complexity. Comparison of it with the state complexity is carried out here as well as some interesting minimization properties are discussed. It is shown that minimization of the number of states can lead to a superpolynomial increase of BC-complexity.
Padding and the expressive power of existential second-order logics
1998
Padding techniques are well-known from Computational Complexity Theory. Here, an analogous concept is considered in the context of existential second-order logics. Informally, a graph H is a padded version of a graph G, if H consists of an isomorphic copy of G and some isolated vertices. A set A of graphs is called weakly expressible by a formula ϕ in the presence of padding, if ϕ is able to distinguish between (sufficiently) padded versions of graphs from A and padded versions of graphs that are not in A.
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^{\varOmega (n/log n)}\) and present quantum OBD…
If P ≠ NP then Some Strongly Noninvertible Functions Are Invertible
2001
Rabi, Rivest, and Sherman alter the standard notion of noninvertibility to a new notion they call strong noninvertibility, and show--via explicit cryptographic protocols for secret-key agreement ([RS93, RS97] attribute this to Rivest and Sherman) and digital signatures [RS93, RS97]--that strongly noninvertible functions would be very useful components in protocol design. Their definition of strong noninvertibility has a small twist ("respecting the argument given") that is needed to ensure cryptographic usefulness. In this paper, we show that this small twist has a large, unexpected consequence: Unless P = NP, some strongly noninvertible functions are invertible.
Graph connectivity and monadic NP
2002
Ehrenfeucht games are a useful tool in proving that certain properties of finite structures are not expressible by formulas of a certain type. In this paper a new method is introduced that allows the extension of a local winning strategy for Duplicator, one of the two players in Ehrenfeucht games, to a global winning strategy. As an application it is shown that graph connectivity cannot be expressed by existential second-order formulas, where the second-order quantification is restricted to unary relations (monadic NP), even, in the presence of a built-in linear order. As a second application it is stated, that, on the other hand, the presence of a linear order increases the power of monadi…
Dichotomies properties on computational complexity of S-packing coloring problems
2015
This work establishes the complexity class of several instances of the S -packing coloring problem: for a graph G , a positive integer k and a nondecreasing list of integers S = ( s 1 , ? , s k ) , G is S -colorable if its vertices can be partitioned into sets S i , i = 1 , ? , k , where each S i is an s i -packing (a set of vertices at pairwise distance greater than s i ). In particular we prove a dichotomy between NP-complete problems and polynomial-time solvable problems for lists of at most four integers.
On Physical Problems that are Slightly More Difficult than QMA
2013
We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural computational problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian).
If P≠NP then some strongly noninvertible functions are invertible
2006
AbstractRabi, Rivest, and Sherman alter the standard notion of noninvertibility to a new notion they call strong noninvertibility, and show—via explicit cryptographic protocols for secret-key agreement (Rabi and Sherman attribute this protocol to Rivest and Sherman) and digital signatures (Rabi and Sherman)—that strongly noninvertible functions are very useful components in protocol design. Their definition of strong noninvertibility has a small twist (“respecting the argument given”) that is needed to ensure cryptographic usefulness. In this paper, we show that this small twist has a consequence: unless P=NP, some strongly noninvertible functions are invertible.
Two-Variable First-Order Logic with Equivalence Closure
2012
We consider the satisfiability and finite satisfiability problems for extensions of the two-variable fragment of first-order logic in which an equivalence closure operator can be applied to a fixed number of binary predicates. We show that the satisfiability problem for two-variable, first-order logic with equivalence closure applied to two binary predicates is in 2-NExpTime, and we obtain a matching lower bound by showing that the satisfiability problem for two-variable first-order logic in the presence of two equivalence relations is 2-NExpTime-hard. The logics in question lack the finite model property; however, we show that the same complexity bounds hold for the corresponding finite sa…