Now showing items 1-20 of 55

    • The Collapsing Hierarchies 

      Hartmanis, Juris (Cornell University, 1987-09)
      No Abstract Available
    • Complexity Classes Without Machines: On Complete Languages for UP 

      Hartmanis, Juris; Hemachandra, Lane A. (Cornell University, 1986-04)
      This paper develops techniques for studying complexity classes that are not covered by known recursive enumerations of machines. Often, counting classes, probabilistic classes, and intersection classes lack such enumerations. ...
    • 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 ...
    • Computational Complexity of Formal Translations 

      Hartmanis, Juris (Cornell University, 1973-12)
      The purpose of this paper is to define a mathematical model for the study of quantitative problems about translations between universal languages and to investigate such problems. The results derived in this paper deal ...
    • Computational Complexity of One-Tape Turing Machine Computations 

      Hartmanis, Juris (Cornell University, 1968-01)
      This paper is concerned with the quantitative aspects of one-tape Turing machine computations. It is shown, for instance, that there exists a sharp time bound which must be reached for the recognition of non-regular sets ...
    • Computational Complexity of Random Access Stored Program Machines 

      Hartmanis, Juris (Cornell University, 1970-08)
      In this paper we explore the computational complexity measure defined by running times of programs on random access stored program machines, RASP'S. The purpose of this work is to study more realistic complexity measures ...
    • 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 ...
    • Final Report on NSF Research Grant Automata and Computational Complexity 1968-1972 

      Hartmanis, Juris (Principal Investigator) (Cornell University, 1972-08)
      This report summarizes the results obtained in research supported by the National Science Foundation Grant AUTOMATA AND COMPUTATIONAL COMPLEXITY. The report lists the problem areas considered, the publications resulting ...
    • 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 ...
    • Godel, von Neumann and the P=?NP Problem 

      Hartmanis, Juris (Cornell University, 1989-04)
      In a 1956 letter, Godel asked von Neumann about the computational complexity of an NP complete problem. In this column, we review the historic setting of this period, discuss Godel's amazing letter and why von Neumann ...
    • Independence Results about Context-Free Languages and Lower Bounds 

      Hartmanis, Juris (Cornell University, 1984-05)
      We show that for any axiomatizable, sound formal system F there exist instances of natural problems about context-free languages, lower bounds of computations and P versus NP that are not provable in F for any recursive ...
    • 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 ...
    • 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, ...
    • The LBA Problem and its Importance in the Theory of Computing 

      Hartmanis, Juris; Hunt, Harry B., III (Cornell University, 1973-05)
      In this paper we study the classic problem of determining whether the deterministic and non-deterministic context-sensitive languages are the same or, equivalently, whether the languages accepted by deterministic and ...
    • New Developments in Structural Complexity Theory 

      Hartmanis, Juris (Cornell University, 1988-04)
      This paper discusses the scope and goals of structural complexity theory, describes some working hypothesis of this field and summarizes (some) recent development.
    • 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 ...
    • A Note on One-way and Two-way Automata 

      Hartmanis, Juris (Cornell University, 1969-09)
      The purpose of this note is to show that there exist non-regular languages whose memory requirements for recognition by one-way and two-way automata differ by a double exponential and that this difference cannot be exceeded.
    • 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 ...
    • 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 ...
    • 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 ...