One-way functions and the nonisomorphism of NP-complete sets
Open Access
- 22 April 1991
- journal article
- research article
- Published by Elsevier in Theoretical Computer Science
- Vol. 81 (1) , 155-163
- https://doi.org/10.1016/0304-3975(91)90323-t
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- Complexity classes without machines: On complete languages for UPTheoretical Computer Science, 1988
- Isomorphisms and 1-L reductionsJournal of Computer and System Sciences, 1988
- Complexity Measures for Public-Key CryptosystemsSIAM Journal on Computing, 1988
- On one-one polynomial time equivalence relationsTheoretical Computer Science, 1985
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NPTheoretical Computer Science, 1985
- Reductions among polynomial isomorphism typesTheoretical Computer Science, 1985
- Relativized Questions Involving Probabilistic AlgorithmsJournal of the ACM, 1982
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- Relative complexity of checking and evaluatingInformation Processing Letters, 1976
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975