Koepke machines and satisfiability for infinitary propositional languages

DOI10.1007/978-3-319-58741-7_19MaRDI QIDQ2011652zbMATH OpenOpenAlexFDO

Authors Merlin Carl, Benedikt Löwe, Benjamin G. Rin

Publication date 4 August 2017

Full work available at URL http://dspace.library.uu.nl/handle/1874/358640

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Some observations on infinitary complexity
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• P NP for infinite time Turing machines
• Infinite time Turing machines
• Tractable and intractable classes of propositional schemata

Cites work

• P NP for infinite time Turing machines
• scientific article; zbMATH DE number 1908324 (Why is no real title available?)
• scientific article; zbMATH DE number 3206304 (Why is no real title available?)
• Infinite time recognizability from generic oracles and the recognizable jump operator
• Infinite time Turing machines
• Is P = PSPACE for Infinite Time Turing Machines?
• Logical Approaches to Computational Barriers
• Ordinal computability
• Ordinal machines and admissible recursion theory
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• Pf ≠ NPf for almost all f
• The computational strengths of -tape infinite time Turing machines
• Turing Computations On Ordinals

Cited in

(5)

• Some observations on infinitary complexity
• Realisability for infinitary intuitionistic set theory
• scientific article; zbMATH DE number 6528599 (Why is no real title available?)
• Space-bounded OTMs and REG ∞
• Symmetry for transfinite computability

This page was built for publication: Koepke machines and satisfiability for infinitary propositional languages

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