Some Comments on Functional Self-Reducibility and the NP Hierarchy
Permanent Link(s)
Collections
Author
Borodin, Allan B.
Demers, Alan J.
Abstract
In Valiant [11] and Schnorr [9], concepts of "functional self-reducibility" are introduced and investigated. We concentrate on the class NP and on the NP hierarchy of Meyer and Stockmeyer [7] to further investigate these ideas. Assuming that the NP hierarchy exists (specifically, assuming that $P \stackrel{\subset}{+} NP = \sum^{P}{1} \stackrel{\subset}{+} \sum^{P}{2}$ we show that, while every complete set in $\sum^{P}{2}$ is functionally self-reducible, there exist sets in $\sum^{P}{2}$ which are not functionally self-reducible.
Date Issued
1976-07
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR76-284
Type
technical report