Natural Self-Reducible Sets
- 1 October 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 17 (5) , 989-996
- https://doi.org/10.1137/0217062
Abstract
No abstract availableKeywords
This publication has 17 references indexed in Scilit:
- On generalized kolmogorov complexityLecture Notes in Computer Science, 1986
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NPTheoretical Computer Science, 1985
- On self-reducibility and weak P-selectivityJournal of Computer and System Sciences, 1983
- On sparse sets in NP–PInformation Processing Letters, 1983
- Relationship between density and deterministic complexity of MP-complete languagesPublished by Springer Nature ,1978
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- On the Structure of Polynomial Time ReducibilityJournal of the ACM, 1975
- Tally languages and complexity classesInformation and Control, 1974
- Comparing complexity classesJournal of Computer and System Sciences, 1974
- Turing machines and the spectra of first-order formulasThe Journal of Symbolic Logic, 1974