Insignificant choice polynomial time. A logic capturing PTIME

DOI10.1007/978-3-031-99536-1_21MaRDI QIDQ6876446zbMATH OpenFDO

Authors Klaus-Dieter Schewe

Publication date 13 January 2026

Full work available at URL https://doi.org/10.1007/978-3-031-99536-1_21

zbMATH Keywords

abstract state machinedescriptive complexityGurevich's conjectureinsignificant choicenon-determinismpolynomial timePTIME logic

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• A behavioural theory of recursive algorithms
• A new thesis concerning synchronised parallel computing -- simplified parallel ASM thesis
• A unifying logic for non-deterministic, parallel and concurrent abstract state machines
• Abstract State Machines
• An extension of fixpoint logic with a symmetry-based choice construct
• Choiceless polynomial time
• Concurrent abstract state machines
• Elements of finite model theory.
• Evolving Algebras 1993: Lipari Guide
• Fixed-point Logics with Nondeterministic Choice
• scientific article; zbMATH DE number 4009811 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 515735 (Why is no real title available?)
• Relational queries computable in polynomial time
• Sequential abstract-state machines capture sequential algorithms
• Structure and complexity of relational queries

This page was built for publication: Insignificant choice polynomial time. A logic capturing PTIME

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