Hartmanis, Juris
http://hdl.handle.net/1813/14935
2015-10-07T12:51:14ZA Conversation with Juris Hartmanis
http://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.
2010-03-31T00:00:00ZRelative Succinctness of Representations of Languages and Separation of Complexity Classes
http://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
http://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
http://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
http://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
http://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
http://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
http://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
http://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
http://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:00Z