JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing Hartmanis, Juris by Issue Date
Now showing items 2140 of 56

Independence Results in Computer Science
Hartmanis, Juris; Hopcroft, John E. (Cornell University, 197612)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, 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 ... 
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. ... 
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. ... 
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 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 ... 
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 ... 
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 ... 
A Note on Natural Creative Sets and Goedel Numberings
Hartmanis, Juris (Cornell University, 198001)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, 198001)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 OneWay and TwoWay LogTape Automata
Hartmanis, Juris; Mahaney, Stephen R. (Cornell University, 198002)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 twoway, $\log n$tape automata. We show that for the oneway, ... 
On Census Complexity and Sparseness of NP Complete Sets
Hartmanis, Juris; Mahaney, Stephen R. (Cornell University, 198004)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 contextsensitive ... 
An Essay About Research on Sparse NP Complete Sets
Hartmanis, Juris; Mahaney, Stephen R. (Cornell University, 198005)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 SpeedUp and Succinctness of Language Representation
Hartmanis, Juris (Cornell University, 198203)In this note we discuss the similarities and differences between Goedel's result about nonrecursive 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, 198203)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 NPP
Hartmanis, Juris (Cornell University, 198208)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 NPP: EXPTIME Versus NEXPTIME
Hartmanis, Juris; Sewelson, Vivian; Immerman, Neil (Cornell University, 198302)This paper investigates the structural properties of sets in NPP 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, 198303)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, 198309)In this paper we define a generalized, twoparameter, 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 NonIsomorphic NP Complete Sets
Hartmanis, Juris (Cornell University, 198310)In this note we show that if the satisfiability of Boolean formulas of low Kolmogorov complexity can be determined in polynomialtime then there exist NP complete sets that are not polynomialtime isomorphic. Keywords: ...