On the Complexity of the First-order Random Theory

DOI10.1093/logcom/13.2.261zbMath1047.03031MaRDI QIDQ4461932

Wafik Boulos Lotfallah

Publication date: 18 May 2004

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/logcom/13.2.261

zbMATH Keywords

PSPACE-completeness; 0-1 law; complexity of logical theories; logical theory

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03C13: Model theory of finite structures