JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing The Legacy of Cornell Faculty and Staff by Issue Date
Now showing items 2140 of 332

A History of the Summer Session, The First SeventyFive Years, 18921966
Smith, William (1974) 
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 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 ... 
A Note on Tape Bounds for SLA Language Processing
Hartmanis, Juris; Berman, L. (Cornell University, 197505)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 ... 
On Effective Speedup and Long Proofs of Trivial Theorems in Formal Theories
Hartmanis, Juris (Cornell University, 197507)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 ... 
On Isomorphisms and Density of NP and Other Complete Sets
Hartmanis, Juris; Berman, L. (Cornell University, 197510)If all NP complete sets are isomorphic under deterministic polynomial time mappings (pisomorphic) then P $\neq$ NP and if all PTAPE complete sets are pisomorphic then P $\neq$ PTAPE. We show that all NP complete sets ... 
Independence Results in Computer Science
Hartmanis, Juris; Hopcroft, John E. (Cornell University, 197612)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 ... 
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 ... 
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. ... 
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. ... 
On LogTape Isomorphisms of Complete Sets
Hartmanis, Juris (Cornell University, 197707)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. ... 
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 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 ... 
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 ... 
A World Without Disorder: Absolute Zero Temperature  A Robert C. Richardson Lecture
Richardson, Robert C. (InternetFirst University Press, 19790801)Robert C. Richardson's 1978 public lecture, demonstration, "A World Without Disorder: Absolute Zero Temperature", describes for a general audience the research for which later he, along with Lee and Osheroff, would be ... 
A Note on Natural Creative Sets and Goedel Numberings
Hartmanis, Juris (Cornell University, 198001)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 ... 
Observations About the Development of Theoretical Computer Science
Hartmanis, Juris (Cornell University, 198001)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 ... 
Languages Simultaneously Complete for OneWay and TwoWay LogTape Automata
Hartmanis, Juris; Mahaney, Stephen R. (Cornell University, 198002)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 twoway, $\log n$tape automata. We show that for the oneway, ... 
On Census Complexity and Sparseness of NP Complete Sets
Hartmanis, Juris; Mahaney, Stephen R. (Cornell University, 198004)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 contextsensitive ... 
An Essay About Research on Sparse NP Complete Sets
Hartmanis, Juris; Mahaney, Stephen R. (Cornell University, 198005)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 ...