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

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 ... 
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 ... 
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 ... 
Independence Results about ContextFree Languages and Lower Bounds
Hartmanis, Juris (Cornell University, 198405)We show that for any axiomatizable, sound formal system F there exist instances of natural problems about contextfree 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, 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 ... 
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, ... 
The LBA Problem and its Importance in the Theory of Computing
Hartmanis, Juris; Hunt, Harry B., III (Cornell University, 197305)In this paper we study the classic problem of determining whether the deterministic and nondeterministic contextsensitive languages are the same or, equivalently, whether the languages accepted by deterministic and ... 
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. 
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 ... 
A Note on Oneway and Twoway Automata
Hartmanis, Juris (Cornell University, 196909)The purpose of this note is to show that there exist nonregular languages whose memory requirements for recognition by oneway and twoway 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, 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 ... 
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 ... 
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 ... 
On Complete Problems for NP$\cap$CoNP
Hartmanis, Juris; Immerman, Neil (Cornell University, 198504)It is not known whether complete languages exist for $NP\cap CoNP$, and Sipser has shown that there are relativizations so that $NP\cap CoNP$ has no $\leq ^{P}_{m}$complete languages. In this paper we show that $NP\cap ... 
On Effective Speedup and Long Proofs of Trivial Theorems in Formal Theories
Hartmanis, Juris (Cornell University, 197507)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 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 IP=PSPACE and Theorems with Narrow Proofs
Hartmanis, Juris; Chang, Richard; Ranjan, Desh; Rohatgi, Pankaj (Cornell University, 199005)Very recently, it was shown that the class of languages with interactive proofs, IP, is exactly the class PSPACE. This surprising result elegantly places IP in the standard classification of feasible computations. ... 
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 ... 
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 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: ...