Now showing items 21-40 of 56

    • 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 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 ...
    • On Goedel Speed-Up and Succinctness of Language Representation 

      Hartmanis, Juris (Cornell University, 1982-03)
      In this note we discuss the similarities and differences between Goedel's result about non-recursive shortening of proofs of formal systems by additional axioms and the corresponding results about the succinctness of ...
    • On the Structure of Feasible Computations 

      Hartmanis, Juris (Cornell University, 1982-03)
      This paper discusses the study of computational complexity of feasible computations and surveys some recent insights and results about the structure of NP complete languages and the attempts to separate the classic ...
    • On Sparse Sets in NP-P 

      Hartmanis, Juris (Cornell University, 1982-08)
      The main result of this note shows that there exist sparse sets in $NP$ that are not in $P$ if and only if NEXPTIME differs from EXPTIME. Several other results are derived about the complexity of very sparse sets in ...
    • Sparse Sets in NP-P: EXPTIME Versus NEXPTIME 

      Hartmanis, Juris; Sewelson, Vivian; Immerman, Neil (Cornell University, 1983-02)
      This paper investigates the structural properties of sets in NP-P and shows that the computational difficulty of lower density sets in NP depends explicitly on the relations between higher deterministic and nondeterministic ...
    • Computation Times of NP Sets of Different Densities 

      Hartmanis, Juris; Yesha, Yaacov (Cornell University, 1983-03)
      In this paper, we study the computational complexity of sets of different densities in NP. We show that the deterministic computation time for sets in NP can depend on their density if and only if there is a collapse or ...
    • Generalized Kolmogorov Complexity and the Structure of Feasible Computations 

      Hartmanis, Juris (Cornell University, 1983-09)
      In this paper we define a generalized, two-parameter, Kolmogorov complexity of finite strings which measures how much and how fast a string can be compressed and we show that this string complexity measure is an efficient ...
    • On Non-Isomorphic NP Complete Sets 

      Hartmanis, Juris (Cornell University, 1983-10)
      In this note we show that if the satisfiability of Boolean formulas of low Kolmogorov complexity can be determined in polynomial-time then there exist NP complete sets that are not polynomial-time isomorphic. Keywords: ...