eCommons Collection:
http://hdl.handle.net/1813/14935
2015-01-30T14:02:53ZRelative Succinctness of Representations of Languages and Separation of Complexity Classes
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:00ZOne-Way Log-Tape Reductions
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:00ZOn the Succintness of Different Representations of Languages
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:00ZOn Log-Tape Isomorphisms of Complete Sets
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:00ZOn Polynomial Time Isomorphism of Complete Sets
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:00ZOn Isomorphisms and Density of NP and Other Complete Sets
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:00ZRelations Between Diagonalization, Proof Systems, and Complexity Gaps
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:00ZA Note on Tape Bounds for SLA Language Processing
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:00ZStructural Complexity Theory: Recent Surprises
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:00ZGodel, von Neumann and the P=?NP Problem
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