Author :
D. Niwinski;A. Stolboushkin
Author_Institution :
Inst. of Inf., Warsaw Univ., Poland
Abstract :
It is shown that no formula of first-order logic using linear ordering and the logical relation y=2x can define the property that the size of a finite model is divisible by 3. This answers a long-standing question that may be of relevance to certain open problems in circuit complexity.
Keywords :
"Complexity theory","Informatics","Ear","Polynomials","Logic circuits","Computer science","Mathematics"
Conference_Titel :
Logic in Computer Science, 1993. LICS ´93., Proceedings of Eighth Annual IEEE Symposium on
Print_ISBN :
0-8186-3140-6
DOI :
10.1109/LICS.1993.287590
