Hartmanis, Juris
https://hdl.handle.net/1813/14935
2020-02-28T13:05:26ZA Conversation with Juris Hartmanis
https://hdl.handle.net/1813/14934
A Conversation with Juris Hartmanis
Hartmanis, Juris
Juris Hartmanis is video taped in a far-reaching conversation (70 minutes) with colleague David Gries. They discuss Hartmanis’ childhood and family background and his immigration to the United States. Next they trace his extraordinary career at the GE Research Laboratory, where he collaborated with Richard Stearns on pioneering research that eventually was recognized by ACM’s prestigious, highest honor – the Turing Award. After having served earlier as an Instructor in Cornell’s Mathematics Department, Juris returned to Cornell as a full professor and the founding chair of a new department of Computer Science. This Department was embedded in two colleges, Engineering
and Arts and Sciences. Cornell was among the first Universities to establish a Department of Computer Science. His pioneering work on computational
complexity blossomed into a new field and under his leadership the Computer Science department matured into a robust, national leader with a strong theoretical emphasis.
After a successful stint at the National Science Foundation leading the transition
of the academic research network NSFnet to become the Internet, he returned to Cornell. At Cornell he continues an active program of research and maintains a leadership role in developing information technologies that have become a ubiquitous element across the entire Cornell academic scene.; Juris Hartmanis joined Cornell in 1965 as the founding chair of the new Department of Computer Science. One
of the first CS departments (the first started in 1964), CS was embedded in two colleges, Engineering and Arts &
Sciences. Under his leadership, CS matured into a robust, national leader with a strong theoretical emphasis.
Juris came from GE, where he collaborated with Richard Stearns on pioneering research that was later recognized
by ACM’s prestigious, highest honor: the Turing Award. Fittingly, Juris is known as “the father of computational
complexity”. He is a member of the NAE and NAS, has honorary doctorates, and received the Grand Medal of the
Latvian Academy of Sciences.
Like most of the CS faculty, Juris spent time in the service of the CS community. He chaired a National Research
Council Study, resulting in the book “Computing the Future”. In 1996-1998, he was Assistant Director of the NSF
Directorate of Computer and Information Science and Engineering (CISE).
In this conversation (70 minutes), Juris and David talk about his childhood, his family background, his immigration
to the US, and his career.
Running Time: 70 min. http://hdl.handle.net/1813/14934
2010-03-31T00:00:00ZRelative Succinctness of Representations of Languages and Separation of Complexity Classes
https://hdl.handle.net/1813/7467
Relative Succinctness of Representations of Languages and Separation of Complexity Classes
Hartmanis, Juris
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 relative succintness of different representations of languages is directly related to the separation of the corresponding complexity classes; for example, PTIME $\neq$ NPTIME if and only if the relative succintness of representing languages in PTIME by deterministic and nondeterministic clocked polynomial time machines is not recursively bound which happens if and only if the relative succintness of these representations is not linearly bounded.
1978-08-01T00:00:00ZOne-Way Log-Tape Reductions
https://hdl.handle.net/1813/7465
One-Way Log-Tape Reductions
Hartmanis, Juris; Immerman, Neil; Mahaney, Stephen R.
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 classes than the P-time [2,7] or log-tape [4] reductions. Although the 1-L computations are provably weaker than the feasible classes L, NL, P and NP, the known complete sets for those classes are complete under 1-L reductions. However, using known techniques of counting arguments and recursion theory we show that certain log-tape reductions cannot be 1-L and we construct sets that are complete under log-tape reductions but not under 1-L reductions.
1978-07-01T00:00:00ZOn the Succintness of Different Representations of Languages
https://hdl.handle.net/1813/7464
On the Succintness of Different Representations of Languages
Hartmanis, Juris
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 to derive some new results about how the relative succintness of representations change when the representations contain a formal proof that the languages generated are in the desired subclass of languages.
1978-06-01T00:00:00ZOn Log-Tape Isomorphisms of Complete Sets
https://hdl.handle.net/1813/7439
On Log-Tape Isomorphisms of Complete Sets
Hartmanis, Juris
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. As an application of these results we obtain easy to check necessary and sufficient conditions that sets complete under $\log n$-tape reductions in NL, CSL, P, NP, PTAPE, etc. are $\log n$-tape isomorphic to the previously known complete sets in the respective classes. As a matter of fact, all the "known" complete sets for NL, CSL, P, NP, PTAPE, etc. are now easily seen to be, respectively, $\log n$-tape isomorphic. These results strengthen and extend substantially the previously known results about polynomial time computable reductions and isomorphisms of NP and PTAPE complete sets. Furthermore, we show that any set complete in CSL, PTAPE, etc. must be dense and therefore, for example, cannot be over a single letter alphabet.
1977-07-01T00:00:00ZOn Polynomial Time Isomorphism of Complete Sets
https://hdl.handle.net/1813/7111
On Polynomial Time Isomorphism of Complete Sets
Berman, L.; Hartmanis, Juris
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 time isomorphic to the previously known complete sets in the corresponding categories.
1976-12-01T00:00:00ZOn Isomorphisms and Density of NP and Other Complete Sets
https://hdl.handle.net/1813/7101
On Isomorphisms and Density of NP and Other Complete Sets
Hartmanis, Juris; Berman, L.
If all NP complete sets are isomorphic under deterministic polynomial time mappings (p-isomorphic) then P $\neq$ NP and if all PTAPE complete sets are p-isomorphic then P $\neq$ PTAPE. We show that all NP complete sets known (in the literature) are indeed p-isomorphic and so are the known PTAPE complete sets. Thus showing that, in spite of the radically different origins and attempted simplification of these sets, all the known NP complete sets are identical but for polynomially time bounded permutations. Furthermore, if all NP complete sets are p-isomorphic then they must have similar densities and, for example, no language over a single letter alphabet can be NP complete, nor can any sparse language over an arbitrary alphabet be NP complete. We show that complete sets in EXPTIME and EXPTAPE cannot be sparse and therefore they cannot be over a single letter alphabet. Similarly, we show that the hardest context-sensitive languages cannot be sparse. We also relate the existence of sparse complete sets to the existence of simple combinatorial circuits for the corresponding truncated recognition problem of these languages.
1975-10-01T00:00:00ZRelations Between Diagonalization, Proof Systems, and Complexity Gaps
https://hdl.handle.net/1813/7016
Relations Between Diagonalization, Proof Systems, and Complexity Gaps
Hartmanis, Juris
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. This replaces the traditional "clock" in resource bounded diagonalization by formal proofs about running times and establishes close relations between properties of proof systems and existence of sharp time bounds for one-tape Turing machine complexity classes. Furthermore, these diagonalization methods show that the Gap Theorem for resource bounded computations does not hold for complexity classes consisting only of languages accepted by Turing machines for which it can be formally proven that they run in the required time bound.
1977-03-01T00:00:00ZA Note on Tape Bounds for SLA Language Processing
https://hdl.handle.net/1813/6988
A Note on Tape Bounds for SLA Language Processing
Hartmanis, Juris; Berman, L.
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 bounded complexity classes of sla languages between log n and log log n tape bounds. We also show that every infinite sla language recognizable on less than log n tape has infinitely many different regular subsets, and, therefore, the set of primes in unary notation, P, requires exactly log n tape for its recognition and every infinite subset of P requires at least log n tape.
1975-05-01T00:00:00ZStructural Complexity Theory: Recent Surprises
https://hdl.handle.net/1813/6957
Structural Complexity Theory: Recent Surprises
Hartmanis, Juris; Chang, Richard; Ranjan, Desh; Rohatgi, Pankaj
This paper reviews the impact of some recent results on the research paradigms in structural complexity theory.
1990-04-01T00:00:00ZGodel, von Neumann and the P=?NP Problem
https://hdl.handle.net/1813/6910
Godel, von Neumann and the P=?NP Problem
Hartmanis, Juris
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 did not solve the P = ?NP problem.
1989-04-01T00:00:00ZOn the Importance of Being II2-Hard
https://hdl.handle.net/1813/6877
On the Importance of Being II2-Hard
Hartmanis, Juris
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 independence results, b) non-recursive succinctness relations between different representations of languages, c) the existence of incomplete languages in various complexity classes.
1989-01-01T00:00:00ZSpace Bounded Computations: Review And New Separation Results
https://hdl.handle.net/1813/6802
Space Bounded Computations: Review And New Separation Results
Hartmanis, Juris; Ranjan, Desh
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, the low level deterministic and nondeterministic space bounded complexity classes are different. Furthermore, for this computation model, we show that Savitch and Immerman-Szelepcsenyi theorems do not hold in the range lg lg $n$ to lg $n$. We also discuss some other computation models to bring out and clarify the importance of space constructability and establish some results about these models. We conclude by enumerating a few open problems which arise out of the discussion.
1989-05-01T00:00:00ZStructural Complexity Column: Some Observations About Relativization of Space Bounded Computations
https://hdl.handle.net/1813/6752
Structural Complexity Column: Some Observations About Relativization of Space Bounded Computations
Hartmanis, Juris
NO ABSTRACT AVAILABLE
1988-05-01T00:00:00ZNew Developments in Structural Complexity Theory
https://hdl.handle.net/1813/6748
New Developments in Structural Complexity Theory
Hartmanis, Juris
This paper discusses the scope and goals of structural complexity theory, describes some working hypothesis of this field and summarizes (some) recent development.
1988-04-01T00:00:00ZThe Collapsing Hierarchies
https://hdl.handle.net/1813/6701
The Collapsing Hierarchies
Hartmanis, Juris
No Abstract Available
1987-09-01T00:00:00ZStructural Complexity Column for the Bulletin of the European Association for Theoretical Computer Science
https://hdl.handle.net/1813/6679
Structural Complexity Column for the Bulletin of the European Association for Theoretical Computer Science
Hartmanis, Juris
Abstract not Available
1987-06-01T00:00:00ZSome Observations About NP Complete Sets
https://hdl.handle.net/1813/6657
Some Observations About NP Complete Sets
Hartmanis, Juris
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.
1987-03-01T00:00:00ZOne-Way Functions, Robustness, and the Non-Isomorphism of NP-Complete Sets
https://hdl.handle.net/1813/6636
One-Way Functions, Robustness, and the Non-Isomorphism of NP-Complete Sets
Hartmanis, Juris; Hemachandra, Lane A.
This paper 1. gives a relativized counterexample to the conjectured connection between the existence of one-way functions and the existence of non-isomorphic NP-complete sets. 2. establishes that in relativized worlds there are NP-complete sets that are non-isomorphic in a strong sense. 3. proves that robust machines squander their powerful nondeterministic oracle access in all relativizations. (1) resolves an open question. (2) extends our knowledge about non-isomorphic NP-complete sets. (3) sharing the proof techniques of (1) and (2), enriches the nascent theory of robustness and presents a consequence of the limited combinatorial control of machines.
1986-01-01T00:00:00ZComplexity Classes Without Machines: On Complete Languages for UP
https://hdl.handle.net/1813/6586
Complexity Classes Without Machines: On Complete Languages for UP
Hartmanis, Juris; Hemachandra, Lane A.
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. Concentrating on the counting class UP, we show that there are relativizations for which $UP^{A}$ has no complete languages and other relativizations for which $P^{B} \neq UP^{B} \neq NP^{B}$ and $UP^{B}$ has complete languages. Among other results we show that $P \neq UP$ if and only if there exists a set $S$ in $P$ of Boolean formulas with at most one satisfying assignment such that $S \bigcap SAT$ is not in $P$. $P \neq UP \bigcap coUP$ if and only if there exists a set $S$ in $P$ of uniquely satisfiable Boolean formulas such that no polynomial-time machine can compute the solutions for the formulas in $S$. If $UP$ has complete languages then there exists a set $R$ in $P$ of Boolean formulas with at most one satisfying assignment so that $SAT \bigcap R$ is complete for $UP$. Finally, we indicate the wide applicability of our techniques to counting and probabilistic classes by using them to examine the probabilistic class $BPP$. There is a relativized world where $BPP^{A}$ has no complete languages. If $BPP$ has complete languages then it has a complete language of the form $B \bigcap MAJORITY$, where $B \in P$ and $MAJORITY = \{f | f$ is true for at least half of all assignments\} is the canonical $PP$-complete set.
1986-04-01T00:00:00ZRelations Between Diagonalization, Proof Systems, and Complexity Gaps
https://hdl.handle.net/1813/6561
Relations Between Diagonalization, Proof Systems, and Complexity Gaps
Hartmanis, Juris
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. This replaces the traditional "clock" in resource bounded diagonalization by formal proofs about running times and establishes close relations between properties of proof systems and existence of sharp time bounds for one-tape Turing machine complexity classses. These diagonalization methods also show that the Gap Theorem for resource bounded computations can hold only for those complexity classes which differ from the corresponding provable complexity classes. Furthermore, we show that there exist recursive time bounds $T(n)$ such that the class of languages for which we can formally prove the existence of Turing machines which accept them in time $T(n)$ differs form the class of languages accepted by Turing machines for which we can prove formally that they run in time $T(n)$.
1977-06-01T00:00:00ZOn Sparse Oracles Separating Feasible Complexity Classes
https://hdl.handle.net/1813/6547
On Sparse Oracles Separating Feasible Complexity Classes
Hartmanis, Juris; Hemachandra, Lane A.
This note clarifies which oracles separate NP from P and which do not. In essence, we are changing our research paradigm from the study of which problems can be relativized in two conflicting ways to the study and characterization of the class of oracles achieving a specified relativization. Results of this type have the potential to yield deeper insights into the nature of relativization problems and focus our attention on new and interesting classes of languages. A complete and transparent characterization of oracles that separate NP from P would resolve the long-standing P =? NP question. In this note, we settle a central case. We fully characterize the sparse oracles separating NP from P in worlds where P = NP. We display related results about coNP, E, NE, coNE, and PSPACE.
1985-10-01T00:00:00ZOn Complete Problems for NP$\cap$CoNP
https://hdl.handle.net/1813/6510
On Complete Problems for NP$\cap$CoNP
Hartmanis, Juris; Immerman, Neil
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 CoNP$ has $\leq ^{P}_{m}$-complete languages if and only if it has $\leq ^{P}_{T}$-complete languages. Furthermore, we show that if a complete language $L_{0}$ exists for $NP\cap CoNP$ and $NP\cap CoNP \neq NP$ then the reduction of $L(N_{i}) \in NP\cap CoNP$ cannot be effectively computed from $N_{i}$. We extend the relativization results by exhibiting an oracle $E$ such that $P^{E} \neq NP^{E} \cap CoNP^{E} \neq NP^{E}$ and for which there exist complete languages in the intersection. For this oracle the reduction to a complete language can be effectively computed from complementary pairs of machines $(N_{i}, N_{j})$ such that $L(N_{i})= \overline{L(N_{j})}$. On the other hand, there also exist oracles $F$ such that $P^{F} \neq NP^{F} \cap CoNP^{F} \neq NP^{F}$ for which the intersection has complete languages, but the reductions to the complete language cannot be effectively computable from the complementary pairs of machines. In this case, the reductions can be computed from $(N_{i}, N_{j}$, Proof that $L(N_{i})= \overline{L(N_{j})}).$
1985-04-01T00:00:00ZIndependence Results about Context-Free Languages and Lower Bounds
https://hdl.handle.net/1813/6446
Independence Results about Context-Free Languages and Lower Bounds
Hartmanis, Juris
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 representqation of these problems. Most previous independence results in computer science have been proven for specific representations of the problems, by exploiting the "opaqueness" of Turing machine names. Our results rely on the complexity of the logical structure of the problem and yield independence results which do not depend on the representations of problems. We show, for example, that there exists a non-regular context-free language $L_{o}$ such that for no cf-grammar $G, L(G) = L_{o}$, it is provable in F that "L(G) is not regular". We also show, among other results P and NP, that there exists a recursive oracle A such that $NP^{A} \neq P^{A}$, and that this fact is not provable in F for any recursive representation of A. The difference of what is and is not provable in F is well illustrated by questions about polynomial time isomorphisms (p-isomorphisms) of NP complete sets. We show that for every NP complete set, L, there is a representation of L by a non-deterministic polynomial time machine for which we can prove that L is NP complete. Furthermore if L is p-isomorphic to SAT then this is also provable in F for some representation of L. On the other hand, if there exist NP complete sets not p-isomorphic to SAT then there exists an NP complete set L for which, independent of its representation, there is no proof in F that L is or is not p-isomorphic to SAT.
1984-05-01T00:00:00ZOn Non-Isomorphic NP Complete Sets
https://hdl.handle.net/1813/6416
On Non-Isomorphic NP Complete Sets
Hartmanis, Juris
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: NP complete sets, isomorphism, Kolmogorov complexity.
1983-10-01T00:00:00ZGeneralized Kolmogorov Complexity and the Structure of Feasible Computations
https://hdl.handle.net/1813/6413
Generalized Kolmogorov Complexity and the Structure of Feasible Computations
Hartmanis, Juris
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 tool for the study of computational complexity. The advantage of this approach is that it not only classifies strings as random or not random, but measures the amount of randomness detectable in a given time. This permits the study how computations change the amount of randomness of finite strings and thus establish a direct link between computational complexity and generalized Kolmogorov complexity of strings. This approach gives a new viewpoint for computational complexity theory, yields natural formulations of new problems and yields new results about the structure of feasible computations.
1983-09-01T00:00:00ZComputation Times of NP Sets of Different Densities
https://hdl.handle.net/1813/6388
Computation Times of NP Sets of Different Densities
Hartmanis, Juris; Yesha, Yaacov
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 partial collapse of the corresponding higher nondeterministic and deterministic time bonded complexity classes. We show also that for NP sets of different densities there exist complete sets of the corresponding density under polynomial time Turing reductions. Finally, we show that these results can be interpreted as results about the complexity of theorem proving and proof presentation in axiomatized mathematical systems. This interpretation relates fundamental questions about the complexity of our intellectual tools to basic structural problems about P, NP, CoNP, and PSPACE, discussed in this paper.
1983-03-01T00:00:00ZSparse Sets in NP-P: EXPTIME Versus NEXPTIME
https://hdl.handle.net/1813/6384
Sparse Sets in NP-P: EXPTIME Versus NEXPTIME
Hartmanis, Juris; Sewelson, Vivian; Immerman, Neil
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 time-bounded complexity classes. The paper exploits the recently discovered upward sparation method, which shows for example that there exist sparse sets in NP-P if and only if EXPTIME $\neq$ NEXPTIME. In addition, the paper uses relativization techniques to determine logical possibilities, limitations of these proof techniques, and, for the first time, to exhibit structural differences between relativized NP and CoNP.
1983-02-01T00:00:00ZOn Sparse Sets in NP-P
https://hdl.handle.net/1813/6348
On Sparse Sets in NP-P
Hartmanis, Juris
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 $NP-P$ and an interpretation of the meaning of these results is given in terms of the complexity of solving "individual instances" of problems in $NP-P$.
1982-08-01T00:00:00ZOn Goedel Speed-Up and Succinctness of Language Representation
https://hdl.handle.net/1813/6325
On Goedel Speed-Up and Succinctness of Language Representation
Hartmanis, Juris
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 different representations of languages.
1982-03-01T00:00:00ZOn the Structure of Feasible Computations
https://hdl.handle.net/1813/6324
On the Structure of Feasible Computations
Hartmanis, Juris
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 complexity classes DLOGTAPE, NDLOGTAPE, PTIME, NPTIME,$\ldots,\Sigma^{P}_{k}, \ldots,$ PTAPE.
1982-03-01T00:00:00ZAn Essay About Research on Sparse NP Complete Sets
https://hdl.handle.net/1813/6262
An Essay About Research on Sparse NP Complete Sets
Hartmanis, Juris; Mahaney, Stephen R.
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 recent solution of this conjecture.
1980-05-01T00:00:00ZOn Census Complexity and Sparseness of NP Complete Sets
https://hdl.handle.net/1813/6256
On Census Complexity and Sparseness of NP Complete Sets
Hartmanis, Juris; Mahaney, Stephen R.
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 languages and $\log n$-tape bounded languages.
1980-04-01T00:00:00ZLanguages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
https://hdl.handle.net/1813/6253
Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
Hartmanis, Juris; Mahaney, Stephen R.
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, $\log n$-tape automata the nondeterministic model (1-NL) is computationally much more powerful than the deterministic model (1-L); that under one-way, $\log n$-tape reductions there exist natural complete languages for these automata and that the complete languages cannot be sparse. Furthermore, we show that any language complete for nondeterministic one-way $\log n$-tape automata (under 1-L reductions) is also complete for the computationally more powerful nondeterministic two-way, $\log n$-tape reductions. Therefore, for all bounds $T(n),T(n \geq \log n$, the deterministic and nondeterministic $T(n)$-tape bounded computations collapse if the nondeterministic one-way $\log n$-tape computations can be carried out by two-way deterministic $\log n$-tape automata.
1980-02-01T00:00:00ZA Note on Natural Creative Sets and Goedel Numberings
https://hdl.handle.net/1813/6245
A Note on Natural Creative Sets and Goedel Numberings
Hartmanis, Juris
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 as equivalent, on the other hand, we intuitively perceive some creative sets as more "natural and simpler" than others. In this note, we try to capture this intuitive concept precisely by defining a creative set to be natural if all other recursively enumerable sets can be reduced to it by computationally simple reductions and show that these natural creative sets are all isomorphic under the same type of computationally simple mappings. The same ideas are also applied to define natural Goedel numberings.
1980-01-01T00:00:00ZObservations About the Development of Theoretical Computer Science
https://hdl.handle.net/1813/6244
Observations About the Development of Theoretical Computer Science
Hartmanis, Juris
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 author, it discusses the underlying beliefs and philosophy which guided this research as well as the intellectual environment and the ideas and contacts which influenced it. An attempt is also made to draw some general conclusions about computer science research and to discuss the nature of theoretical computer science.
1980-01-01T00:00:00ZOn Effective Speed-up and Long Proofs of Trivial Theorems in Formal Theories
https://hdl.handle.net/1813/6239
On Effective Speed-up and Long Proofs of Trivial Theorems in Formal Theories
Hartmanis, Juris
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 of trivially true theorems which require as long proofs in the given formalism as the hardest theorems of the theory. Thus showing that for these theories every formalism is doomed to be blind to the triviality of infinite sets of theorems, which can be found effectively. Furthermore, it follows that for all (sufficiently large) constructable tape and time bounds there exists sets whose recognition can be effectively speeded up on infinite subsets and that such sets appear naturally, thus showing that for many concrete problems, every algorithm can be effectively sped-up on infinite subsets.
1975-07-01T00:00:00ZOn the Intellectual Terrain Around NP
https://hdl.handle.net/1813/6180
On the Intellectual Terrain Around NP
Hartmanis, Juris; Chari, Suresh
In this paper, we view $P \stackrel{?}{=} NP$ as the problem which symbolizes the attempt to understand what is and what is not feasibly computable. The paper shortly reviews the history of the developments from Godel's 1956 letter asking for the computational complexity of finding proofs of theorems, through computational complexity, the exploration of complete problems for NP and PSPACE, through the results of structural complexity to the recent insights about interactive proofs.
1993-12-01T00:00:00ZIndependence Results in Computer Science
https://hdl.handle.net/1813/6063
Independence Results in Computer Science
Hartmanis, Juris; Hopcroft, John E.
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 cannot be answered in formalized set theory, that explicit algorithms can be given whose running time is independent of the axioms of set theory, and that one can exhibit a specific context-free grammar G for which it cannot be proven in set theory that $L(G) = \sum^{\*}$ or $L(G) \neq \sum^{\*}$.
1976-12-01T00:00:00ZOn the Power of Multiplication in Random Access Machines
https://hdl.handle.net/1813/6053
On the Power of Multiplication in Random Access Machines
Hartmanis, Juris; Simon, Janos
We consider random access machines with a multiplication operation, having the added capability of computing logical operations on bit vectors in parallel. The contents of a register are considered both as an integer and as a vector of bits and both arithmetic and boolean operations may be used on the same register. We prove that, counting one operation as a unit of time and considering the machines as acceptors, deterministic and non-deterministic polynomial time acceptable languages are the same, and are exactly the languages recognizable in polynomial tape by Turing machines. We observe that the same measure on machines without multiplication is polynomially related to Turing machine time - thus the added computational power due to multiplication in random access machines is equivalent to the computaitonal power which polynomially tape-bounded Turing machine computations have over polynomially time-bounded computations. Therefore, in this formulation, it is not harder to multiply than to add if and only if PTAPE=PTIME for Turing machines. We also discuss other instruction sets for random access machines and their computational power.
1974-09-01T00:00:00ZOn the Structure of Feasible Computations
https://hdl.handle.net/1813/6050
On the Structure of Feasible Computations
Hartmanis, Juris; Simon, Janos
During the last four years research on the lower level computational complexity has yielded a rich set of interesting results which have revealed deep and unexpected connections between various problems and thus brought new unity to this area of computer science. This work has also yielded new techniques and insights which are likely to have further applications, and it has identified some very central problems in the quantitative theory of computing. The purpose of this paper is to give the reader an overview of these developments, an insight into some of these results and applications, as well as an appreciation of the unity and structure which has emerged in this area of research.
1974-08-01T00:00:00ZComputational Complexity of Formal Translations
https://hdl.handle.net/1813/6034
Computational Complexity of Formal Translations
Hartmanis, Juris
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 with the efficiency of the translated algorithms, the optimality of translations and the complexity of the translation process between different languages. Keywords: universal languages, Goedel numberings, translations, complexity of translations, optimality, length of translated programs.
1973-12-01T00:00:00ZOn Simple Goedel Numberings and Translations
https://hdl.handle.net/1813/6022
On Simple Goedel Numberings and Translations
Hartmanis, Juris; Baker, Theodore Paul
In this paper we consider Goedel numberings (viewed as simple models for programming languages) into which all other Goedel numberings can be translated very easily. Several such classes of Goedel numberings are defined and their properties are investigated. We also compare these classes of Goedel numberings to optimal Goedel numberings and show that translation into optimal Goedel numberings can be computationally arbitrarily complex.
1973-07-01T00:00:00ZOn the Problem of Finding Natural Computational Complexity Measures
https://hdl.handle.net/1813/6018
On the Problem of Finding Natural Computational Complexity Measures
Hartmanis, Juris
To develop an abstract theory which deals with the quantitative aspects of computing we need a deeper understanding of how to define "natural" computational complexity measures axiomatically. To this end, this paper summarizess the principal properties which hold for some natural complexity measures but not for all measures and which have been proposed as desirable properties of natural measuress. The paper discusses the nature of these properties, studies their interrelations and their possible values towards defining natural computational complexity measures. A number off open problems are discussed and directions for further research are suggested.
1973-06-01T00:00:00ZThe LBA Problem and its Importance in the Theory of Computing
https://hdl.handle.net/1813/6015
The LBA Problem and its Importance in the Theory of Computing
Hartmanis, Juris; Hunt, Harry B., III
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 non-deterministic linearly bounded automata are the same. We show that this problem is equivalent to several other natural problems in the theory of computing and that the techniques used on the LDA problem have several other applications in complexity theory. For example, we show that there exists a hardest-tape recognizable non-deterministic context-sensitive language $L_{1}$, such that $L_{1}$ is a deterministic context-sensitive language if and only if the deterministic and non-deterministic context-sensitive languages are the same. We show furthermore, that many decision problems about sets described by regular expressions are instances of these tape-hardest recognizable context-sensitive languages. Thus, it follows that non-determinism in Turing machine computations (using at least linear tape) can not save memory over deterministic Turing machine computations if and only if the equivalence of regular expressions can be decided by a deterministic linearly bounded automaton. It also follows that the equivalence of regular expressions can be decided by a non-deterministic linearly bounded automaton if and only if the family of context-sensitive languages is closed under complementation.
1973-05-01T00:00:00ZFinal Report on NSF Research Grant Automata and Computational Complexity 1968-1972
https://hdl.handle.net/1813/5996
Final Report on NSF Research Grant Automata and Computational Complexity 1968-1972
Hartmanis, Juris (Principal Investigator)
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 from this work and gives an outline of the more recent research results which have not yet been published.
1972-08-01T00:00:00ZSize Arguments in the Study of Computation Speeds
https://hdl.handle.net/1813/5932
Size Arguments in the Study of Computation Speeds
Hartmanis, Juris
In this paper we use arguments about the size of the computed functions to investigate the computation speed of Turing machines. It turns out that the size arguments yield several new results which we have not been able to obtain previously by diagonalization. For example, we show that for arbitrarily complex running times $T(n)$ there exist functions which can be computed on a one-tape Turing machine in time $T(n)$ but not in time $t(n)$ provided $\stackrel{\lim}{n \rightarrow \infty} \frac{t(n)}{T(n)}=0$. The same result is also shown to hold for many-tape machines. We show furthermore, that there exist arbitrarily complex computations for which one-tape machines are slower than two-tape machines by a factor equal to the logarithm of the computation time of the two-tape machine. We conclude by discussing several other computational complexity measures and compare results obtained by diagonalization and size arguments.
1970-08-01T00:00:00ZComputational Complexity of Random Access Stored Program Machines
https://hdl.handle.net/1813/5929
Computational Complexity of Random Access Stored Program Machines
Hartmanis, Juris
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 and to provide a setting and some techniques to explore different computer organizations. The more interesting results of this paper are obtained by an argument about the size of the computed functions. For example, we show (without using diagonalization) that there exist arbitrarily complex functions with optimal RASP programs whose running time cannot be improved by any multiplicative constant. We show, furthermore, that these optimal programs cannot be fixed prodecures and self-modifying programs. The same technique is used to compare computation speed of machines with and without built in multiplication. We conclude the paper with a look at machines with associative memory and distributed logic machines.
1970-08-01T00:00:00ZAn Overview of the Theory of Computational Complexity
https://hdl.handle.net/1813/5918
An Overview of the Theory of Computational Complexity
Hartmanis, Juris; Hopcroft, John E.
The purpose of this paper is to outline the theory of computational complexity which has emerged as a comprehensive theory during the last decade. This theory is concerned with the quantitative aspects of computations and its central theme is the measuring of the difficulty of computing functions. The paper does not attempt to give an exhaustive survey but instead presents the basic concepts, results and techniques of computational complexity from a new point of view from which the ideas are more easily understood and fit together as a coherant whole.
1970-04-01T00:00:00ZThe Use of Lists in the Study of Undecidable Problems in Automata Theory
https://hdl.handle.net/1813/5912
The Use of Lists in the Study of Undecidable Problems in Automata Theory
Hartmanis, Juris; Lewis, Forbes
NO ABSTRACT SUPPLIED
1970-01-01T00:00:00ZA Note on One-way and Two-way Automata
https://hdl.handle.net/1813/5901
A Note on One-way and Two-way Automata
Hartmanis, Juris
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.
1969-09-01T00:00:00ZTape Reversal Bounded Turing Machine Computations
https://hdl.handle.net/1813/5884
Tape Reversal Bounded Turing Machine Computations
Hartmanis, Juris
This paper studies the classification of recursive sets by the number of tape reversals required for their recognition on a two-tape Turing machine with a one-way input tape. This measure yields a rich hierarchy of tape reversal limited complexity classes and their properties and ordering are investigated. The most striking difference between this and the previously studied complexity measures lies in the fact that the "speed-up" theorem does not hold for slowly growing tape reversal complexity classes. These differences are discussed, and several relations between the different complexity measures and languages are established.
1968-02-01T00:00:00ZComputational Complexity of One-Tape Turing Machine Computations
https://hdl.handle.net/1813/5880
Computational Complexity of One-Tape Turing Machine Computations
Hartmanis, Juris
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 of sequences. It is shown that the computation time can be used to characterize the complexity of recursive sets of sequences and several results are obtained about this classification. These results are then applied to the recognition speed of context-free languages and it is shown, among other things, that it is recursively undecidable how much time is required to recognize a non-regular context-free language on a one-tape Turing machine. Several unsolved problems are discussed.
1968-01-01T00:00:00ZTwo Memory Bounds for the Recognition of Primes by Automata
https://hdl.handle.net/1813/5874
Two Memory Bounds for the Recognition of Primes by Automata
Hartmanis, Juris; Shank, H.
Two Memory Bounds for the Recognition of Primes by Automata
1968-06-01T00:00:00ZRefinement of Hierarchies of Time Bounded Computations
https://hdl.handle.net/1813/5873
Refinement of Hierarchies of Time Bounded Computations
Hartmanis, Juris; Hopcroft, John E.
It is shown that for any "slowly growing" time function $T(n)$ and any $\epsilon > 0$ there exists a computation which can be performed by a multitape Turing machine in time $T(n)\log^{\epsilon}T(n)$ and cannot be performed by any multitape Turing machine in time $T(n)$.
1968-06-01T00:00:00ZOn the Recognition of Primes by Automata
https://hdl.handle.net/1813/5864
On the Recognition of Primes by Automata
Hartmanis, Juris; Shank, H.
A study of the problem of recognizing the set of primes by automata is presented. A simple algebraic condition is derived which shows that neither the set of primes nor any infinite subset of primes can be accepted by a pushdown or finite automaton. In view of this result an interesting open problem is to determine the "weakest" automaton which can accept the set of primes. It is shown that the linearly bounded automaton can accept the set of primes, and it is conjectured that no automaton whose memory grows less rapidly can recognize the set of primes. One of the results shows that if this conjecture is true, it cannot be proved by the use of arguments about the distribution of primes, as described by the Prime Number Theorem. Some relations are established between two classical conjectures in number theory and the minimal rate of memory growth of automata which can recognize the set of primes.
1968-02-01T00:00:00Z