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

DOI10.2178/JSL/1045861507MaRDI QIDQ4457727zbMATH OpenOpenAlexFDO

Authors 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

Random graphs (graph-theoretic aspects) (05C80) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Turing machines and related notions (03D10)

Recommendations

• Polynomial-time axioms of choice and polynomial-time cardinality
• scientific article; zbMATH DE number 1670468
• Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
• Addendum to ``Choiceless polynomial time
• Strong 0-1 laws in finite model theory
• Fixed-Point Definability and Polynomial Time
• scientific article; zbMATH DE number 4119625
• A new zero-one law and strong extension axioms
• scientific article; zbMATH DE number 2155182
• scientific article; zbMATH DE number 17551

Cites work

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

Cited in

(9)

• Zero-one law and definability of linear order
• scientific article; zbMATH DE number 1670468 (Why is no real title available?)
• Is polynomial time choiceless?
• Symbioses between mathematical logic and computer science
• scientific article; zbMATH DE number 2155182 (Why is no real title available?)
• Addendum to ``Choiceless polynomial time
• Zero-one laws and almost sure valuations of first-order logic in semiring semantics
• Functional Thesauri, Classifying Topoi, Unification, and Flatness
• Choiceless computation and symmetry

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

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