Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
Open Access
- 31 December 1985
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 39, 225-237
- https://doi.org/10.1016/0304-3975(85)90140-9
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- Optimal Approximations and Polynomially Levelable SetsSIAM Journal on Computing, 1986
- Reductions among polynomial isomorphism typesTheoretical Computer Science, 1985
- Polynomial time computations in models of ETJournal of Computer and System Sciences, 1983
- Completeness, Approximation and DensitySIAM Journal on Computing, 1981
- A note on structure and looking back applied to the relative complexity of computable functionsJournal of Computer and System Sciences, 1981
- Indexings of subrecursive classesTheoretical Computer Science, 1980
- Simple Gödel Numberings, Isomorphisms, and Programming PropertiesSIAM Journal on Computing, 1978
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975
- Optimal enumerations and optimal gödel numberingsTheory of Computing Systems, 1974