Name
Abstract | ||
|---|---|---|
A. Cobham (1964) presented a machine-independent characterization of computational feasibility, via inductive definition. R. Constable (1973) was apparently the first to consider the notion of feasibility for type 2 functionals. K. Mehlhorn's (1976) study of feasible reducibilities proceeds from Constable's work. Here, a class of polytime operators is defined, using a generalization of Cobham's definition. The authors provide an affirmative answer to the question of whether there is a natural machine based definition of Mehlhorn's class. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1109/SFCS.1991.185389 | FOCS |
Keywords | DocType | ISBN |
polynomial time,feasibility | Conference | 0-8186-2445-0 |
Citations | PageRank | References |
1 | 0.36 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bruce M. Kapron | 1 | 308 | 26.02 |
| Stephen Cook | 2 | 4864 | 2433.99 |