Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Self-reducibility structures and solutions of np problems

Autor
Balcazar, J. L.
Tipus d'activitat
Article en revista
Revista
Revista matemática de la Universidad Complutense de Madrid
Data de publicació
1989-12
Volum
2
Número
3
Pàgina inicial
175
Pàgina final
184
DOI
https://doi.org/10.5209/rev_REMA.1989.v2.n2.18114 Obrir en finestra nova
URL
http://www.mat.ucm.es/serv/revmat/vol2-23/vol2-23b.pdf Obrir en finestra nova
Resum
Using polynomnial 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 funcilonal NP-complete problems, and extend this relationships to the case of optimization NP-complete problems.
Grup de recerca
LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge

Participants