Name
Title | ||
|---|---|---|
Syntactic Characterization in LISP of the Polynominal Complexity Classes and Hierarchy |
Abstract | ||
|---|---|---|
. The definition of a class C of functions is syntactic if membershipto C can be decided from the construction of its elements. Syntacticcharacterizations of PTIMEF, of PSPACEF, of the polynomial hierarchyPH, and of its subclasses \Deltapn are presented. They are obtained byprogressive restrictions of recursion in Lisp, and may be regarded aspredicative according to a foundational point raised by Leivant.1 IntroductionAt least since 1965 [6] people think to complexity in terms of... |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1007/3-540-62592-5_61 | CIAC |
Keywords | Field | DocType |
polynominal complexity classes,syntactic characterization,complexity class | PH,Polynomial hierarchy,Complexity class,Discrete mathematics,Structural complexity theory,Primitive recursive function,Computer science,Lisp,Descriptive complexity theory,Predicative expression | Conference |
Volume | ISSN | ISBN |
1203 | 0302-9743 | 3-540-62592-5 |
Citations | PageRank | References |
2 | 0.41 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Salvatore Caporaso | 1 | 17 | 5.11 |
| Michele Zito | 2 | 35 | 3.76 |
| Nicola Galesi | 3 | 367 | 28.05 |
| Emanuele Covino | 4 | 11 | 5.80 |