A logic for PTIME and a parameterized halting problem

DOI10.1007/978-3-642-15025-8_14MaRDI QIDQ3586007zbMATH OpenOpenAlexFDO

Authors Yijia Chen, Jörg Flum

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

zbMATH Keywords

halting problemslogics for PTIMEparameterized complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)

Recommendations

• A Parameterized Halting Problem
• Is there a logic for polynomial time?
• A parameterized halting problem, the linear time hierarchy, and the MRDP theorem
• Is polynomial time choiceless?
• Computation Models for Parameterized Complexity

Cites work

• Almost every set in exponential time is P-bi-immune
• Database Theory - ICDT 2005
• Fixed Structure Complexity
• scientific article; zbMATH DE number 4008383 (Why is no real title available?)
• On the complexity of Gödel's proof predicate
• Relational queries computable in polynomial time
• Relativizations comparing NP and exponential time
• Structure and complexity of relational queries

Cited in

(8)

• A Parameterized Halting Problem
• PARTIAL HALTING IN P SYSTEMS
• Fixed-Point Definability and Polynomial Time
• scientific article; zbMATH DE number 1424054 (Why is no real title available?)
• A restricted second-order logic for non-deterministic poly-logarithmic time
• A parameterized halting problem, the linear time hierarchy, and the MRDP theorem
• From almost optimal algorithms to logics for complexity classes via listings and a halting problem
• A surprising relationship between descriptive complexity and proof complexity

This page was built for publication: A logic for PTIME and a parameterized halting problem

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