Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Straight-Line Programs:
TR95-022 | 2nd May 1995
Marek Karpinski, Wojciech Rytter, Ayumi Shinohara

Pattern-Matching for Strings with Short Descriptions

We consider strings which are succinctly described. The description
is in terms of straight-line programs in which the constants are
symbols and the only operation is the concatenation. Such
descriptions correspond to the systems of recurrences or to
context-free grammars generating single words. The descriptive ... more >>>

TR03-018 | 28th March 2003
Matthias Galota, Heribert Vollmer

Functions Computable in Polynomial Space

We show that the class of integer-valued functions computable by
polynomial-space Turing machines is exactly the class of functions f
for which there is a nondeterministic polynomial-time Turing
machine with a certain order on its paths that on input x outputs a 3x3
matrix with entries from {-1,0,1} on each ... more >>>

TR05-037 | 8th April 2005
Eric Allender, Peter B├╝rgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen

On the Complexity of Numerical Analysis

Revisions: 1 , Comments: 1

We study two quite different approaches to understanding the complexity
of fundamental problems in numerical analysis. We show that both hinge
on the question of understanding the complexity of the following problem,
which we call PosSLP:
Given a division-free straight-line program
producing an integer N, decide whether N>0.
more >>>

ISSN 1433-8092 | Imprint