Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR03-025 | 14th April 2003
Kristoffer Arnsfelt Hansen

Constant width planar computation characterizes ACC0

We obtain a characterization of ACC0 in terms of a natural class of
constant width circuits, namely in terms of constant width polynomial
size planar circuits. This is shown via a characterization of the
class of acyclic digraphs which can be embedded on a cylinder surface
in such a way ... more >>>


TR03-023 | 12th February 2003
Anna Palbom

On Spanning Cacti and Asymmetric TSP

In an attempt to generalize Christofides algorithm for metric TSP to the asymmetric TSP with triangle inequality we have studied various properties of directed spanning cacti. In this paper we first observe that finding the TSP in a directed, weighted complete graph with triangle inequality is polynomial time equivalent to ... more >>>


TR03-024 | 25th February 2003
Till Tantau

Weak Cardinality Theorems for First-Order Logic

Kummer's cardinality theorem states that a language is recursive
if a Turing machine can exclude for any n words one of the
n + 1 possibilities for the number of words in the language. It
is known that this theorem does not hold for polynomial-time
computations, but there ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint