Koepke machines and satisfiability for infinitary propositional languages

DOI10.1007/978-3-319-58741-7_19zbMATH Open1436.03218OpenAlexW2612962042MaRDI QIDQ2011652FDOQ2011652

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

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

Recommendations

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

Cites work

• 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 Turing machines
• Infinite time recognizability from generic oracles and the recognizable jump operator
• 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 \(\alpha\)-tape infinite time Turing machines
• Turing Computations On Ordinals
• \(P\neq NP\) for infinite time Turing machines

Cited in

(5)

• Symmetry for transfinite computability
• Realisability for infinitary intuitionistic set theory
• Title not available (Why is no real title available?)
• Some observations on infinitary complexity
• Space-bounded OTMs and REG ∞

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)