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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Infinite time Turing machines
• Ordinal machines and admissible recursion theory
• Turing Computations On Ordinals
• Ordinal computability
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• Pf ≠ NPf for almost all f
• Logical Approaches to Computational Barriers
• \(P\neq NP\) for infinite time Turing machines
• The computational strengths of \(\alpha\)-tape infinite time Turing machines
• Is P = PSPACE for Infinite Time Turing Machines?
• Infinite time recognizability from generic oracles and the recognizable jump operator

Cited In (5)

• Symmetry for transfinite computability
• Realisability for infinitary intuitionistic set theory
• Title not available (Why is that?)
• 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)