✦ LIBER ✦

On the computational complexity of the order polynomial

✍ Scribed by Ulrich Faigle; Rainer Schrader

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 370 KB
Volume: 15
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(86)90047-8

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the polynomial IO-complexity

✍ JoséD.P. Rolim 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 808 KB

Computing the jump number on semi-orders

Computing the jump number on semi-orders is polynomial

✍ A. von Arnim; C. de la Higuera 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 870 KB

On the computational complexity of graph

On the computational complexity of graph closures

✍ Angelo Monti 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 375 KB

On the computational complexity of infin

On the computational complexity of infinite words

✍ Pavol Ďuriš; Ján Maňuch 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 132 KB

On the cell probe complexity of polynomi

On the cell probe complexity of polynomial evaluation

✍ Peter Bro Miltersen 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 461 KB

The quantifier complexity of polynomial-

The quantifier complexity of polynomial-size iterated definitions in first-order logic

✍ Samuel R. Buss; Alan S. Johnson 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 208 KB

## Abstract We refine the constructions of Ferrante‐Rackoff and Solovay on iterated definitions in first‐order logic and their expressibility with polynomial size formulas. These constructions introduce additional quantifiers; however, we show that these extra quantifiers range over only finite set