Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Turing machines:
TR96-063 | 6th November 1996
Martin Dietzfelbinger

The Linear-Array Problem in Communication Complexity Resolved

Tiwari (1987) considered the following scenario: k+1 processors P_0,...,P_k,
connected by k links to form a linear array, compute a function f(x,y), for
inputs (x,y) from a finite domain X x Y, where x is only known to P_0 and
y is only known to P_k; the intermediate ... more >>>

TR00-075 | 7th September 2000
Andreas Klein, Martin Kutrib

Deterministic Turing Machines in the Range between Real-Time and Linear-Time

Deterministic k-tape and multitape Turing machines with one-way,
two-way and without a separated input tape are considered. We
investigate the classes of languages acceptable by such devices with
time bounds of the form n+r(n) where r in o(n) is a sublinear
function. It is shown that there ... more >>>

TR11-071 | 27th April 2011
Serge Gaspers, Stefan Szeider

The Parameterized Complexity of Local Consistency

Revisions: 1

We investigate the parameterized complexity of deciding whether a constraint network is $k$-consistent. We show that, parameterized by $k$, the problem is complete for the complexity class co-W[2]. As secondary parameters we consider the maximum domain size $d$ and the maximum number $\ell$ of constraints in which a variable occurs. ... more >>>

ISSN 1433-8092 | Imprint