Using self-reducibilities to characterize polynomial time (Q2366567)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 227136
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Using self-reducibilities to characterize polynomial time |
scientific article; zbMATH DE number 227136 |
Statements
Using self-reducibilities to characterize polynomial time (English)
0 references
30 August 1993
0 references
The effect of a set having a self-reducibility structure is studied. Three variations on the notion of Turing self-reducibility are studied: near-testability, word-decreasing self-reducibility, and \(p\)- cheatability. The complexity class of polynomial-time computable sets is characterized in several non-trivial ways using the above notions. In the concluding section several research questions building upon this work are posed.
0 references
self-reducibility
0 references
near-testability
0 references
\(p\)-cheatability
0 references
polynomial-time computable sets
0 references
0.8074526786804199
0 references
0.8057147860527039
0 references
