scientific article

zbMath0705.68053MaRDI QIDQ3993545

K. Ruediger Reischuk

Publication date: 23 January 1993

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Turing machinesNP-completenesscircuitsparallel computerscomplexity theoryrandom access machinescomplete problemsprocessor networkstime versus place problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Pattern matching in trace monoids ⋮ Linear speed-up does not hold on Turing machines with tree storages ⋮ Unambiguity of circuits ⋮ Foundations of \(r\)-contiguous matching in negative selection for anomaly detection ⋮ Time-space tradeoffs for satisfiability ⋮ On computation with pulses