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

On Polynomial Time Isomorphism of Complete Sets
Berman, L.; Hartmanis, Juris (Cornell University, 197612)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 ... 
On Simple Goedel Numberings and Translations
Hartmanis, Juris; Baker, Theodore Paul (Cornell University, 197307)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 ... 
On Sparse Oracles Separating Feasible Complexity Classes
Hartmanis, Juris; Hemachandra, Lane A. (Cornell University, 198510)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 ... 
On Sparse Sets in NPP
Hartmanis, Juris (Cornell University, 198208)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 ... 
On the Importance of Being II2Hard
Hartmanis, Juris (Cornell University, 198901)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 ... 
On the Intellectual Terrain Around NP
Hartmanis, Juris; Chari, Suresh (Cornell University, 199312)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 ... 
On the Power of Multiplication in Random Access Machines
Hartmanis, Juris; Simon, Janos (Cornell University, 197409)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 ... 
On the Problem of Finding Natural Computational Complexity Measures
Hartmanis, Juris (Cornell University, 197306)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 ... 
On the Recognition of Primes by Automata
Hartmanis, Juris; Shank, H. (Cornell University, 196802)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 ... 
On the Structure of Feasible Computations
Hartmanis, Juris; Simon, Janos (Cornell University, 197408)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 ... 
On the Structure of Feasible Computations
Hartmanis, Juris (Cornell University, 198203)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 ... 
On the Succintness of Different Representations of Languages
Hartmanis, Juris (Cornell University, 197806)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 contextfree languages and ... 
OneWay Functions, Robustness, and the NonIsomorphism of NPComplete Sets
Hartmanis, Juris; Hemachandra, Lane A. (Cornell University, 198601)This paper 1. gives a relativized counterexample to the conjectured connection between the existence of oneway functions and the existence of nonisomorphic NPcomplete sets. 2. establishes that in relativized worlds ... 
OneWay LogTape Reductions
Hartmanis, Juris; Immerman, Neil; Mahaney, Stephen R. (Cornell University, 197807)Oneway logtape (1L) reductions are mappings defined by logtape Turing machines whose read head on the input can only move to the right. The 1L reductions provide a more refined tool for studying the feasible complexity ... 
An Overview of the Theory of Computational Complexity
Hartmanis, Juris; Hopcroft, John E. (Cornell University, 197004)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 ... 
Refinement of Hierarchies of Time Bounded Computations
Hartmanis, Juris; Hopcroft, John E. (Cornell University, 196806)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 ... 
Relations Between Diagonalization, Proof Systems, and Complexity Gaps
Hartmanis, Juris (Cornell University, 197706)In this paper we study diagonal processes over timebounded computations of onetape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. ... 
Relations Between Diagonalization, Proof Systems, and Complexity Gaps
Hartmanis, Juris (Cornell University, 197703)In this paper we study diagonal processes over timebounded computations of onetape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. ... 
Relative Succinctness of Representations of Languages and Separation of Complexity Classes
Hartmanis, Juris (Cornell University, 197808)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 ... 
Size Arguments in the Study of Computation Speeds
Hartmanis, Juris (Cornell University, 197008)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 ...