OnP-subset structures
- 1 December 1987
- journal article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 20 (1) , 129-136
- https://doi.org/10.1007/bf01692061
Abstract
No abstract availableKeywords
This publication has 16 references indexed in Scilit:
- Bi-immune sets for complexity classesTheory of Computing Systems, 1985
- Oracle-dependent properties of the lattice of NP setsTheoretical Computer Science, 1983
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979
- On splitting recursive setsJournal of Computer and System Sciences, 1978
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- On the structure of complete sets: Almost everywhere complexity and infinitely often speedupPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- On Reducibility to Complex or Sparse SetsJournal of the ACM, 1975
- Unit Refutations and Horn SetsJournal of the ACM, 1974
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971