Now showing items 19-38 of 56

• #### Observations About the Development of Theoretical Computer Science ﻿

(Cornell University, 1980-01)
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 ...
• #### On Census Complexity and Sparseness of NP Complete Sets ﻿

(Cornell University, 1980-04)
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 context-sensitive ...
• #### On Complete Problems for NP$\cap$CoNP ﻿

(Cornell University, 1985-04)
• #### On the Power of Multiplication in Random Access Machines ﻿

(Cornell University, 1974-09)
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 ﻿

(Cornell University, 1973-06)
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 ﻿

(Cornell University, 1968-02)
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 ﻿

(Cornell University, 1974-08)
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 ﻿

(Cornell University, 1982-03)
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 ...