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

José L. BALCÁZAR
Department of Software
(Lenguajes y Sistemas Informáticos)
Universidad Politécnica de Cataluña
08028 Barcelona Spain
 

Received: December 5, 1988
ABSTRACT

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.