SELF-SPECIFYING MACHINES
From MaRDI portal
Publication:5249003
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)
computational complexityquery orderacceptance mechanismscounting-based computationself-specifying machines
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (2)
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
