Unambiguous computations and locally definable acceptance types

DOI10.1016/S0304-3975(97)00005-4MaRDI QIDQ1127545zbMATH OpenFDO

Authors Rolf Niedermeier, Peter Rossmanith

Publication date 13 August 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

structural complexitycomputation treesunambiguous computation

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 512853
• Locally definable acceptance types for polynomial time machines
• Promise problems and access to unambiguous computation
• Hierarchical Unambiguity

Cites work

• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• scientific article; zbMATH DE number 3984573 (Why is no real title available?)
• scientific article; zbMATH DE number 512853 (Why is no real title available?)
• scientific article; zbMATH DE number 761756 (Why is no real title available?)
• A survey of one-way functions in complexity theory
• A uniform approach to define complexity classes
• Alternation
• Complexity Measures for Public-Key Cryptosystems
• Complexity classes without machines: on complete languages for UP
• Counting classes: Thresholds, parity, mods, and fewness
• Gap-definable counting classes
• Locally definable acceptance types for polynomial time machines
• Logspace and logtime leaf languages
• On the construction of parallel computers from various basis of Boolean functions
• On the power of parity polynomial time
• Promise problems and access to unambiguous computation
• Relative complexity of checking and evaluating
• Robust algorithms: a different approach to oracles
• Robust machines accept easy sets
• The complexity of combinatorial problems with succinct input representation
• The complexity of promise problems with applications to public-key cryptography
• Unambiguity of circuits
• Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
• Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
• Using inductive counting to simulate nondeterministic computation

Cited in

(8)

• Locally definable acceptance types for polynomial time machines
• Promise problems and access to unambiguous computation
• On the probabilistic closure of the loose unambiguous hierarchy
• On the power of unambiguity in alternating machines
• Languages polylog-time reducible to dot-depth 1/2
• Machines that can output empty words
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 1414307 (Why is no real title available?)

This page was built for publication: Unambiguous computations and locally definable acceptance types

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1127545)