Now showing items 1-3 of 3

    • A Note on Tape Bounds for SLA Language Processing 

      Hartmanis, Juris; Berman, L. (Cornell University, 1975-05)
      In this note we show that the tape bounded complexity classes of languages over single letter alphabets are closed under complementation. We then use this result to show that there exists an infinite hierarchy of tape ...
    • On Isomorphisms and Density of NP and Other Complete Sets 

      Hartmanis, Juris; Berman, L. (Cornell University, 1975-10)
      If all NP complete sets are isomorphic under deterministic polynomial time mappings (p-isomorphic) then P $\neq$ NP and if all PTAPE complete sets are p-isomorphic then P $\neq$ PTAPE. We show that all NP complete sets ...
    • On Polynomial Time Isomorphism of Complete Sets 

      Berman, L.; Hartmanis, Juris (Cornell University, 1976-12)
      IN this note we show that the recently discovered NP complete sets arising in number theory, the PTAPE complete sets arising in game theory and EXPTAPE complete sets arising from algebraic word problems are polynomial ...