SELF-SPECIFYING MACHINES

DOI10.1142/S0129054199000198zbMath1319.68083MaRDI QIDQ5249003

Harald Hempel, Hemaspaandra, Lane A., Gerd Wechsung

Publication date: 29 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexityquery orderacceptance mechanismscounting-based computationself-specifying machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

A second step towards complexity-theoretic analogs of Rice's Theorem ⋮ Query Order

Cites Work

• The complexity of computing the permanent
• Qualitative relativizations of complexity classes
• On the construction of parallel computers from various basis of Boolean functions
• Some observations on the connection between counting and recursion
• The complexity of optimization problems
• Reductions on NP and p-selective sets
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• A uniform approach to define complexity classes
• A comparison of polynomial time reducibilities
• Gap-definable counting classes
• Universally serializable computation
• Logspace and logtime leaf languages
• The power of the middle bit of a \(\#\)P function
• Defying upward and downward separation
• A complexity theory for feasible closure properties
• A note on parallel queries and the symmetric-difference hierarchy.
• On the unique satisfiability problem
• Quantitative Relativizations of Complexity Classes
• The Complexity of Enumeration and Reliability Problems
• On Sets with Efficient Implicit Membership Tests
• PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• Query Order
• THE COMPLEXITY OF FINDING MIDDLE ELEMENTS
• Complexity-Restricted Advice Functions
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• Threshold Computation and Cryptographic Security
• On balanced versus unbalanced computation trees
• On the power of parity polynomial time

This page was built for publication: SELF-SPECIFYING MACHINES