Using self-reducibilities to characterize polynomial time (Q2366567)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Using self-reducibilities to characterize polynomial time |
scientific article |
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
