Now showing items 21-40 of 332

    • On the Structure of Feasible Computations 

      Hartmanis, Juris; Simon, Janos (Cornell University, 1974-08)
      During the last four years research on the lower level computational complexity has yielded a rich set of interesting results which have revealed deep and unexpected connections between various problems and thus brought ...
    • On the Power of Multiplication in Random Access Machines 

      Hartmanis, Juris; Simon, Janos (Cornell University, 1974-09)
      We consider random access machines with a multiplication operation, having the added capability of computing logical operations on bit vectors in parallel. The contents of a register are considered both as an integer and ...
    • 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 Effective Speed-up and Long Proofs of Trivial Theorems in Formal Theories 

      Hartmanis, Juris (Cornell University, 1975-07)
      In this note we give a very simple proof which shows that in many interesting formal mathematical theories, axiomatizable as well as decidable ones, for every given formalization we can effectively find infinite subsets ...
    • 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 ...
    • Independence Results in Computer Science 

      Hartmanis, Juris; Hopcroft, John E. (Cornell University, 1976-12)
      In this note we show that instances of problems which appear naturally in computer science cannot be answered in formalized set theory. We show, for example, that some relativized versions of the famous P = NP problem ...
    • 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 ...
    • Relations Between Diagonalization, Proof Systems, and Complexity Gaps 

      Hartmanis, Juris (Cornell University, 1977-03)
      In this paper we study diagonal processes over time-bounded computations of one-tape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. ...
    • Relations Between Diagonalization, Proof Systems, and Complexity Gaps 

      Hartmanis, Juris (Cornell University, 1977-06)
      In this paper we study diagonal processes over time-bounded computations of one-tape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. ...
    • On Log-Tape Isomorphisms of Complete Sets 

      Hartmanis, Juris (Cornell University, 1977-07)
      In this paper we study $\log n$-tape computable reductions between sets and investigate conditions under which $\log n$-tape reductions between sets can be extended to $\log n$-tape computable isomorphisms of these sets. ...
    • On the Succintness of Different Representations of Languages 

      Hartmanis, Juris (Cornell University, 1978-06)
      The purpose of this paper is to give simple new proofs of some interesting recent results about the relative succintness of different representations of regular, deterministic and unambiguous context-free languages and ...
    • One-Way Log-Tape Reductions 

      Hartmanis, Juris; Immerman, Neil; Mahaney, Stephen R. (Cornell University, 1978-07)
      One-way log-tape (1-L) reductions are mappings defined by log-tape Turing machines whose read head on the input can only move to the right. The 1-L reductions provide a more refined tool for studying the feasible complexity ...
    • Relative Succinctness of Representations of Languages and Separation of Complexity Classes 

      Hartmanis, Juris (Cornell University, 1978-08)
      In this paper we study the relative succinctness of different representations of polymomial time languages and investigate what can and cannot be formally verified about these representations. We also show that the ...
    • A World Without Disorder: Absolute Zero Temperature - A Robert C. Richardson Lecture 

      Richardson, Robert C. (Internet-First University Press, 1979-08-01)
      Robert C. Richardson's 1978 public lecture, demonstration, "A World Without Disorder: Absolute Zero Temperature", describes for a general audience the research for which later he, along with Lee and Osheroff, would be ...
    • A Note on Natural Creative Sets and Goedel Numberings 

      Hartmanis, Juris (Cornell University, 1980-01)
      Creative sets (or the complete recursively enumerable sets) play an important role in logic and mathematics and they are known to be recursively isomorphic. Therefore, on the one hand, all the creative sets can be viewed ...
    • Observations About the Development of Theoretical Computer Science 

      Hartmanis, Juris (Cornell University, 1980-01)
      This paper gives a personal account of some developments in automata theory and computational complexity theory. Though the account is subjective and deals primarily with the research areas of direct interest to the ...
    • Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata 

      Hartmanis, Juris; Mahaney, Stephen R. (Cornell University, 1980-02)
      In this paper we study languages accepted by nondeterministic $\log n$-tape automata which scan their input only once and relate their computational power to two-way, $\log n$-tape automata. We show that for the one-way, ...
    • On Census Complexity and Sparseness of NP Complete Sets 

      Hartmanis, Juris; Mahaney, Stephen R. (Cornell University, 1980-04)
      In this note we show that if there are sparse NP complete sets with a polynomial time computable census function then $P=NP$. We also derive related results about the complexity of the census function for context-sensitive ...
    • An Essay About Research on Sparse NP Complete Sets 

      Hartmanis, Juris; Mahaney, Stephen R. (Cornell University, 1980-05)
      The purpose of this paper is to review the origins and motivation for the conjecture that sparse NP complete sets do not exist (unless P=NP) and to describe the development of the ideas and techniques which led to the ...