Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with computability:
TR97-055 | 22nd September 1997
Bruce Edward Litow

A Decision Method for the Rational Sequence Problem

We give a method to decide whether or not an
ordinary finite order linear recurrence with constant, rational
coefficients ever generates zero.

more >>>

TR08-031 | 14th January 2008
James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers

Computability and Complexity in Self-Assembly

This paper explores the impact of geometry on computability =
and complexity in
Winfree's model of nanoscale self-assembly. We work in the =
tile assembly model, i.e., in the discrete Euclidean plane Z x Z. Our =
main theorem says that there is a roughly quadratic function f ... more >>>

TR11-014 | 3rd February 2011
Antoine Taveneaux

Towards an axiomatic system for Kolmogorov complexity

Revisions: 1

In \cite{shenpapier82}, it is shown that four basic functional properties are enough to characterize plain Kolmogorov complexity, hence obtaining an axiomatic characterization of this notion. In this paper, we try to extend this work, both by looking at alternative axiomatic systems for plain complexity and by considering potential axiomatic systems ... more >>>

ISSN 1433-8092 | Imprint