Name
Abstract | ||
|---|---|---|
The complexity classes P=log and Full-P=log, corresponding to the twostandard forms of logarithmic advice for polynomial time, are studied. Thenovel proof technique of "doubly exponential skip" is introduced, and characterizationsfor these classes are found in terms of several other concepts, amongthem easy-to-describe boolean circuits and reduction classes of tally sets withhigh regularity. Similar results hold for many other complexity classes.In this extended abstract most of the... |
Year | Venue | Keywords |
|---|---|---|
1992 | IFIP Congress (1) | logarithmic advice complexity classes,complexity class,boolean circuits,polynomial time |
Field | DocType | Volume |
L,Quantum complexity theory,PH,Complexity class,Discrete mathematics,Structural complexity theory,Computer science,P,Descriptive complexity theory,Alternating Turing machine | Conference | 12 |
ISSN | ISBN | Citations |
0926-5473 | 0-444-89747-X | 13 |
PageRank | References | Authors |
1.02 | 1 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| José L. Balcázar | 1 | 701 | 62.06 |
| Montserrat Hermo | 2 | 55 | 10.77 |
| Elvira Mayordomo | 3 | 500 | 39.46 |