On the complexity of Gödel's proof predicate

DOI10.2178/jsl/1264433918zbMath1201.03050OpenAlexW2116278910MaRDI QIDQ5190198

Jörg Flum, Yijia Chen

Publication date: 15 March 2010

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.570.751

zbMATH Keywords

fixed-parameter tractableproof lengthparametrized complexity theoryparametrized Gödel problem

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items (2)

A Parameterized Halting Problem ⋮ A Logic for PTIME and a Parameterized Halting Problem

Cites Work

• Almost every set in exponential time is P-bi-immune
• Unnamed Item

This page was built for publication: On the complexity of Gödel's proof predicate