Automata, Languages and Programming

DOI10.1007/B99859zbMath1099.68638OpenAlexW2505584480MaRDI QIDQ5466530

Ran Raz, Dieter van Melkebeek

Publication date: 24 August 2005

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b99859

zbMATH Keywords

computational complexitylower boundssatisfiabilitydeterministic Turing machineconondeterministic machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

This page was built for publication: Automata, Languages and Programming