Search results for "Complexity"
showing 10 items of 1094 documents
Finite State Verifiers with Constant Randomness
2012
We give a new characterization of NL as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state machines that use a constant number of random bits, as opposed to its conventional description in terms of deterministic logarithmic-space verifiers. It turns out that allowing two-way interaction with the prover does not change the class of verifiable languages, and that no polynomially bounded amount of randomness is useful for constant-memory computers when used as language recognizers, or public-coin verifiers.
Team learning as a game
1997
A machine FIN-learning machine M receives successive values of the function f it is learning; at some point M outputs conjecture which should be a correct index of f. When n machines simultaneously learn the same function f and at least k of these machines outut correct indices of f, we have team learning [k,n]FIN. Papers [DKV92, DK96] show that sometimes a team or a robabilistic learner can simulate another one, if its probability p (or team success ratio k/n) is close enough. On the other hand, there are critical ratios which mae simulation o FIN(p2) by FIN(p1) imossible whenever p2 _< r < p1 or some critical ratio r. Accordingly to [DKV92] the critical ratio closest to 1/2 rom the let is…
On extremal cases of Hopcroft’s algorithm
2010
AbstractIn this paper we consider the problem of minimization of deterministic finite automata (DFA) with reference to Hopcroft’s algorithm. Hopcroft’s algorithm has several degrees of freedom, so there can exist different executions that can lead to different sequences of refinements of the set of the states up to the final partition. We find an infinite family of binary automata for which such a process is unique, whatever strategy is chosen. Some recent papers (cf. Berstel and Carton (2004) [3], Castiglione et al. (2008) [6] and Berstel et al. (2009) [1]) have been devoted to find families of automata for which Hopcroft’s algorithm has its worst execution time. They are unary automata as…
Counting with Probabilistic and Ultrametric Finite Automata
2014
We investigate the state complexity of probabilistic and ultrametric finite automata for the problem of counting, i.e. recognizing the one-word unary language \(C_n=\left\{ 1^n \right\} \). We also review the known results for other types of automata.
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…
Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
2002
This article presents two algebraic characterizations and two related complete problems for the complexity class DLIN that was introduced in [E. Grandjean, Ann. Math. Artif. Intell., 16 (1996), pp. 183--236]. DLIN is essentially the class of all functions that can be computed in linear time on a Random Access Machine which uses only numbers of linear value during its computations. The algebraic characterizations are in terms of recursion schemes that define unary functions. One of these schemes defines several functions simultaneously, while the other one defines only one function. From the algebraic characterizations, we derive two complete problems for DLIN under new, very strict, and mac…
Application of kolmogorov complexity to inductive inference with limited memory
1995
A b s t r a c t . We consider inductive inference with limited memory[l]. We show that there exists a set U of total recursive functions such that U can be learned with linear long-term memory (and no short-term memory); U can be learned with logarithmic long-term memory (and some amount of short-term memory); if U is learned with sublinear long-term memory, then the short-term memory exceeds arbitrary recursive function. Thus an open problem posed by Freivalds, Kinber and Smith[l] is solved. To prove our result, we use Kolmogorov complexity.
Nondeterministic Unitary OBDDs
2017
We investigate the width complexity of nondeterministic unitary OBDDs (NUOBDDs). Firstly, we present a generic lower bound on their widths based on the size of strong 1-fooling sets. Then, we present classically “cheap” functions that are “expensive” for NUOBDDs and vice versa by improving the previous gap. We also present a function for which neither classical nor unitary nondeterminism does help. Moreover, based on our results, we present a width hierarchy for NUOBDDs. Lastly, we provide the bounds on the widths of NUOBDDs for the basic Boolean operations negation, union, and intersection.
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 efficient …