1998/07/15 by Saharon Shelah, Shelah, Saharon
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #cs.LO #math.LO
paper · pdf · doi:10.48550/arxiv.math/9807179
published as in: {Computer Science Logic, 14th International Workshop, CSL 2000, Annual Conference of the EACSL, Fischbachau, Germany, August 21--26, 2000, Proceedings} (2000) 72--125
arxiv created 1998/07/15 · arxiv updated 2009/11/30
Here we deal with the logic of [GuSh 533], which tries to capture polynomial time (for finite models). There it is proved that the logic cannot say much on models with equality only. Here we prove that it cannot say much on models for which we expect it cannot say much, like random enough graphs. This is the result of having a general criterion.