A Parameterized Halting Problem
From MaRDI portal
Publication:2908544
DOI10.1007/978-3-642-30891-8_17zbMath1358.68123MaRDI QIDQ2908544
Publication date: 5 September 2012
Published in: The Multivariate Algorithmic Revolution and Beyond (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-30891-8_17
68Q25: Analysis of algorithms and problem complexity
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Speedup for natural problems and noncomputability
- Complexity classes of equivalence problems revisited
- Complexity classes without machines: on complete languages for UP
- On the parameterized complexity of short computation and factorization
- Optimal proof systems imply complete sets for promise classes
- On an optimal propositional proof system and the structure of easy subsets of TAUT.
- The Turing way to parameterized complexity
- Fixed-Parameter Tractability, Definability, and Model-Checking
- Strong isomorphism reductions in complexity theory
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Fixed Structure Complexity
- A Logic for PTIME and a Parameterized Halting Problem
- On Slicewise Monotone Parameterized Problems and Optimal Proof Systems for TAUT
- On p-Optimal Proof Systems and Logics for PTIME
- Relational queries computable in polynomial time
- Alternation
- The relative efficiency of propositional proof systems
- Computation Models for Parameterized Complexity
- On the complexity of Gödel's proof predicate
- On Computable Numbers, with an Application to the Entscheidungsproblem
