All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 3 Next

Displaying 41 – 60 of 94

Showing per page

New recursive characterizations of the elementary functions and the functions computable in polynomial space.

I. Oitavem (1997)

Revista Matemática de la Universidad Complutense de Madrid

We formulate recursive characterizations of the class of elementary functions and the class of functions computable in polynomial space that do not require any explicit bounded scheme. More specifically, we use functions where the input variables can occur in different kinds of positions ?normal and safe? in the vein of the Bellantoni and Cook's characterization of the polytime functions.

On Existentially First-Order Definable Languages and Their Relation to NP

Bernd Borchert, Dietrich Kuske, Frank Stephan (2010)

RAIRO - Theoretical Informatics and Applications

Under the assumption that the Polynomial-Time Hierarchy does not collapse we show for a regular language L: the unbalanced polynomial-time leaf language class determined by L equals  iff L is existentially but not quantifierfree definable in FO[<, min, max, +1, −1]. Furthermore, no such class lies properly between NP and co-1-NP or NP⊕co-NP. The proofs rely on a result of Pin and Weil characterizing the automata of existentially first-order definable languages.

Polynomial time bounded truth-table reducibilities to padded sets

Vladimír Glasnák (2000)

Commentationes Mathematicae Universitatis Carolinae

We study bounded truth-table reducibilities to sets of small information content called padded (a set is in the class f -PAD of all f -padded sets, if it is a subset of { x 10 f ( | x | ) - | x | - 1 ; x ∈ { 0 , 1 } * } ). This is a continuation of the research of reducibilities to sparse and tally sets that were studied in many previous papers (for a good survey see [HOW1]). We show necessary and sufficient conditions to collapse and separate classes of bounded truth-table reducibilities to padded sets. We prove that depending on two properties of a...

Relating automata-theoretic hierarchies to complexity-theoretic hierarchies

Victor L. Selivanov (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.

Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies

Victor L. Selivanov (2010)

RAIRO - Theoretical Informatics and Applications

We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.

Signed bits and fast exponentiation

Wieb Bosma (2001)

Journal de théorie des nombres de Bordeaux

An exact analysis is given of the benefits of using the non-adjacent form representation for integers (rather than the binary representation), when computing powers of elements in a group in which inverting is easy. By counting the number of multiplications for a random exponent requiring a given number of bits in its binary representation, we arrive at a precise version of the known asymptotic result that on average one in three signed bits in the non-adjacent form is non-zero. This shows that...

Currently displaying 41 – 60 of 94