Full paper in PDF:
$% J. L. Balcázar, Self-reducibility structures and solutions of NP problems,
Rev. Mat. Univ. Complut. Madrid 2 (1989), no. 2, 3, 175–184.%$
Self-reducibility Structures and Solutions of NP Problems
Using polynomial time self-reducibility structures, we characterize certain “helping” notions, show how the characterization provides the main tool for the proof of known relationships between decisional and functional NP-complete problems, and extend this relationships to the case of optimization NP-complete problems.
1980 Mathematics Subject Classification (1985 revision): 68Q15, 68Q05, 03D15.
ACM Classification: F.1.3.