A Logic for PTIME and a Parameterized Halting Problem
From MaRDI portal
Publication:3586007
DOI10.1007/978-3-642-15025-8_14zbMath1287.68061OpenAlexW2278335590MaRDI QIDQ3586007
Publication date: 3 September 2010
Published in: Fields of Logic and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-15025-8_14
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)
Related Items (2)
Cites Work
- Unnamed Item
- Almost every set in exponential time is P-bi-immune
- Structure and complexity of relational queries
- Fixed Structure Complexity
- Relativizations comparing NP and exponential time
- Relational queries computable in polynomial time
- On the complexity of Gödel's proof predicate
- Database Theory - ICDT 2005
This page was built for publication: A Logic for PTIME and a Parameterized Halting Problem