Choiceless polynomial time
From MaRDI portal
Publication:1125059
DOI10.1016/S0168-0072(99)00005-6zbMath0936.03037arXivmath/9705225WikidataQ105978985 ScholiaQ105978985MaRDI QIDQ1125059
Yuri Gurevich, Saharon Shelah, Andreas Blass
Publication date: 13 April 2000
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/9705225
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10) Descriptive complexity and finite models (68Q19)
Related Items
Abstract State Machines with Exact Real Arithmetic, On symmetric circuits and fixed-point logics, Symbioses between mathematical logic and computer science, Choiceless Polynomial Time on Structures with Small Abelian Colour Classes, Unnamed Item, Can abstract state machines be useful in language theory?, Is Polynomial Time Choiceless?, Recursion versus tail recursion over \(\overline{\mathbb{F}}_p\), Unnamed Item, Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs, Database Theory, Yuri, and Me, Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs, Choiceless Computation and Symmetry, Unnamed Item, Addendum to ``Choiceless polynomial time, Why Sets?, Strong extension axioms and Shelah's zero-one law for choiceless polynomial time, Choiceless Logarithmic Space, Fixed-Point Definability and Polynomial Time, Semantic essence of AsmL, 2005 Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '05, Abstract state machines and computationally complete query languages, Computation on structures. Behavioural theory, logic, complexity, On polynomial time computation over unordered structures
