A logic for PTIME and a parameterized halting problem

DOI10.1007/978-3-642-15025-8_14zbMATH Open1287.68061OpenAlexW2278335590MaRDI QIDQ3586007FDOQ3586007

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

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

zbMATH Keywords

parameterized complexityhalting problemslogics for PTIME

Mathematics Subject Classification ID

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

Cites Work

• Relativizations comparing NP and exponential time
• Relational queries computable in polynomial time
• Structure and complexity of relational queries
• Almost every set in exponential time is P-bi-immune
• Title not available (Why is that?)
• Database Theory - ICDT 2005
• Fixed Structure Complexity
• On the complexity of Gödel's proof predicate

Cited In (8)

• Title not available (Why is that?)
• A Parameterized Halting Problem
• 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
• PARTIAL HALTING IN P SYSTEMS
• A surprising relationship between descriptive complexity and proof complexity
• Fixed-Point Definability and Polynomial Time
• A restricted second-order logic for non-deterministic poly-logarithmic time

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)