http://hdl.handle.net/1813/14935 2013-06-20T02:46:25Z http://hdl.handle.net/1813/7467 Title: Relative Succinctness of Representations of Languages and Separation of Complexity Classes Authors: Hartmanis, Juris Abstract: 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:00Z http://hdl.handle.net/1813/7465 Title: One-Way Log-Tape Reductions Authors: Hartmanis, Juris; Immerman, Neil; Mahaney, Stephen R. Abstract: 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:00Z http://hdl.handle.net/1813/7464 Title: On the Succintness of Different Representations of Languages Authors: Hartmanis, Juris Abstract: 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:00Z http://hdl.handle.net/1813/7439 Title: On Log-Tape Isomorphisms of Complete Sets Authors: Hartmanis, Juris Abstract: 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:00Z http://hdl.handle.net/1813/7111 Title: On Polynomial Time Isomorphism of Complete Sets Authors: Berman, L.; Hartmanis, Juris Abstract: 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:00Z http://hdl.handle.net/1813/7101 Title: On Isomorphisms and Density of NP and Other Complete Sets Authors: Hartmanis, Juris; Berman, L. Abstract: 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:00Z http://hdl.handle.net/1813/7016 Title: Relations Between Diagonalization, Proof Systems, and Complexity Gaps Authors: Hartmanis, Juris Abstract: 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:00Z http://hdl.handle.net/1813/6988 Title: A Note on Tape Bounds for SLA Language Processing Authors: Hartmanis, Juris; Berman, L. Abstract: 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:00Z http://hdl.handle.net/1813/6957 Title: Structural Complexity Theory: Recent Surprises Authors: Hartmanis, Juris; Chang, Richard; Ranjan, Desh; Rohatgi, Pankaj Abstract: This paper reviews the impact of some recent results on the research paradigms in structural complexity theory. 1990-04-01T00:00:00Z http://hdl.handle.net/1813/6910 Title: Godel, von Neumann and the P=?NP Problem Authors: Hartmanis, Juris Abstract: 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:00Z