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

DOI10.2178/JSL/1045861507zbMATH Open1045.03039OpenAlexW2116445981MaRDI QIDQ4457727FDOQ4457727

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

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

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)

Cites Work

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

Cited In (9)

• Zero-one law and definability of linear order
• Title not available (Why is that?)
• Symbioses between mathematical logic and computer science
• Choiceless Computation and Symmetry
• Title not available (Why is that?)
• Is Polynomial Time Choiceless?
• 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

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)