Now showing items 11-30 of 56

• #### Independence Results about Context-Free Languages and Lower Bounds ﻿

(Cornell University, 1984-05)
We show that for any axiomatizable, sound formal system F there exist instances of natural problems about context-free languages, lower bounds of computations and P versus NP that are not provable in F for any recursive ...
• #### Independence Results in Computer Science ﻿

(Cornell University, 1976-12)
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 ...
• #### Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata ﻿

(Cornell University, 1980-02)
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 two-way, $\log n$-tape automata. We show that for the one-way, ...
• #### The LBA Problem and its Importance in the Theory of Computing ﻿

(Cornell University, 1973-05)
In this paper we study the classic problem of determining whether the deterministic and non-deterministic context-sensitive languages are the same or, equivalently, whether the languages accepted by deterministic and ...
• #### New Developments in Structural Complexity Theory ﻿

(Cornell University, 1988-04)
This paper discusses the scope and goals of structural complexity theory, describes some working hypothesis of this field and summarizes (some) recent development.
• #### A Note on Natural Creative Sets and Goedel Numberings ﻿

(Cornell University, 1980-01)
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 ...
• #### A Note on One-way and Two-way Automata ﻿

(Cornell University, 1969-09)
The purpose of this note is to show that there exist non-regular languages whose memory requirements for recognition by one-way and two-way automata differ by a double exponential and that this difference cannot be exceeded.
• #### A Note on Tape Bounds for SLA Language Processing ﻿

(Cornell University, 1975-05)
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 ...
• #### 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 Non-Isomorphic NP Complete Sets ﻿

(Cornell University, 1983-10)
In this note we show that if the satisfiability of Boolean formulas of low Kolmogorov complexity can be determined in polynomial-time then there exist NP complete sets that are not polynomial-time isomorphic. Keywords: ...
• #### On Polynomial Time Isomorphism of Complete Sets ﻿

(Cornell University, 1976-12)
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 ﻿

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

(Cornell University, 1985-10)
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 ...