JavaScript is disabled for your browser. Some features of this site may not work without it.
Hartmanis, Juris
Browse by
This collection is intended to bring together in one place materials dealing with the work and legacy of Cornell Professor, Juris Hartmanis, both new materials and those published in other collections in eCommons.
Included here are:
 A Conversation with Juris Hartmanis  Video and Multimedia Presentation
 Papers by Juris Hartmanis
Recent Submissions

Relative Succinctness of Representations of Languages and Separation of Complexity Classes
Hartmanis, Juris (Cornell University, 197808)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 ... 
OneWay LogTape Reductions
Hartmanis, Juris; Immerman, Neil; Mahaney, Stephen R. (Cornell University, 197807)Oneway logtape (1L) reductions are mappings defined by logtape Turing machines whose read head on the input can only move to the right. The 1L reductions provide a more refined tool for studying the feasible complexity ... 
On the Succintness of Different Representations of Languages
Hartmanis, Juris (Cornell University, 197806)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 contextfree languages and ... 
On LogTape Isomorphisms of Complete Sets
Hartmanis, Juris (Cornell University, 197707)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 Polynomial Time Isomorphism of Complete Sets
Berman, L.; Hartmanis, Juris (Cornell University, 197612)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 ... 
On Isomorphisms and Density of NP and Other Complete Sets
Hartmanis, Juris; Berman, L. (Cornell University, 197510)If all NP complete sets are isomorphic under deterministic polynomial time mappings (pisomorphic) then P $\neq$ NP and if all PTAPE complete sets are pisomorphic then P $\neq$ PTAPE. We show that all NP complete sets ... 
Relations Between Diagonalization, Proof Systems, and Complexity Gaps
Hartmanis, Juris (Cornell University, 197703)In this paper we study diagonal processes over timebounded computations of onetape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. ... 
A Note on Tape Bounds for SLA Language Processing
Hartmanis, Juris; Berman, L. (Cornell University, 197505)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 ... 
Structural Complexity Theory: Recent Surprises
Hartmanis, Juris; Chang, Richard; Ranjan, Desh; Rohatgi, Pankaj (Cornell University, 199004)This paper reviews the impact of some recent results on the research paradigms in structural complexity theory. 
Godel, von Neumann and the P=?NP Problem
Hartmanis, Juris (Cornell University, 198904)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 ... 
On the Importance of Being II2Hard
Hartmanis, Juris (Cornell University, 198901)In this column, we show how a variety of interesting results in theory of computation all follow from a simple observation about $\prod _{2}$complete sets of total machines. We easily derive: a) representation independent ... 
Space Bounded Computations: Review And New Separation Results
Hartmanis, Juris; Ranjan, Desh (Cornell University, 198905)In this paper, we review the key results about space bounded complexity classes, discuss the central open problems and outline the relevant proof techniques. We show that, for a slightly modified Turing machine model, ... 
Structural Complexity Column: Some Observations About Relativization of Space Bounded Computations
Hartmanis, Juris (Cornell University, 198805)NO ABSTRACT AVAILABLE 
New Developments in Structural Complexity Theory
Hartmanis, Juris (Cornell University, 198804)This paper discusses the scope and goals of structural complexity theory, describes some working hypothesis of this field and summarizes (some) recent development. 

Structural Complexity Column for the Bulletin of the European Association for Theoretical Computer Science
Hartmanis, Juris (Cornell University, 198706)Abstract not Available 
Some Observations About NP Complete Sets
Hartmanis, Juris (Cornell University, 198703)In this paper we summarize and extend some recent results about the properties of NP complete sets and related results about the structure of feasible computations. 
OneWay Functions, Robustness, and the NonIsomorphism of NPComplete Sets
Hartmanis, Juris; Hemachandra, Lane A. (Cornell University, 198601)This paper 1. gives a relativized counterexample to the conjectured connection between the existence of oneway functions and the existence of nonisomorphic NPcomplete sets. 2. establishes that in relativized worlds ... 
Complexity Classes Without Machines: On Complete Languages for UP
Hartmanis, Juris; Hemachandra, Lane A. (Cornell University, 198604)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. ... 
Relations Between Diagonalization, Proof Systems, and Complexity Gaps
Hartmanis, Juris (Cornell University, 197706)In this paper we study diagonal processes over timebounded computations of onetape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. ...