## Paper: y=2x vs. y=3x (at LICS 1993)

**Damian Niwinski Alexei P. Stolboushkin**

### 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

### BibTeX

@InProceedings{NiwinskiStolboushki-y2xvsy3x, author = {Damian Niwinski and Alexei P. Stolboushkin}, title = {y=2x vs. y=3x}, booktitle = {Proceedings of the Eighth Annual IEEE Symposium on Logic in Computer Science (LICS 1993)}, year = {1993}, month = {June}, pages = {172--178}, location = {Montreal, Canada}, publisher = {IEEE Computer Society Press} }