Strong extension axioms and Shelah's zero-one law for choiceless polynomial time

DOI10.2178/jsl/1045861507zbMath1045.03039OpenAlexW2116445981MaRDI QIDQ4457727

Andreas Blass, Yuri Gurevich

Publication date: 25 March 2004

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/jsl/1045861507

zbMATH Keywords

parallel computationrandom structurezero-one lawsextension axiomschoiceless polynomial spacechoiceless polynomial time machineconstant time computablerandom signa

Mathematics Subject Classification ID

Related Items (5)

Functional Thesauri, Classifying Topoi, Unification, and Flatness ⋮ Symbioses between mathematical logic and computer science ⋮ Is Polynomial Time Choiceless? ⋮ Choiceless Computation and Symmetry ⋮ Zero-one law and definability of linear order

Cites Work

• Unnamed Item
• 0-1 laws and decision problems for fragments of second-order logic
• Choiceless polynomial time
• Properties of almost all graphs and complexes
• A zero-one law for logic with a fixed-point operator
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: Strong extension axioms and Shelah's zero-one law for choiceless polynomial time