Now showing items 1-6 of 6

• #### An Essay About Research on Sparse NP Complete Sets ﻿

(Cornell University, 1980-05)
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 ...
• #### Inexact Agreement: Accuracy, Precision, and Graceful Degradation ﻿

(Cornell University, 1985-05)
An Inexact Agreement protocol alows processors that each have a value approximating $\hat{\nu}$ to compute new values that are closer to each other and close to $\hat{\nu}$. Two fault-tolerant protocols for Inexact ...
• #### 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, ...
• #### 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 ...
• #### One-Way Log-Tape Reductions ﻿

(Cornell University, 1978-07)
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 ...
• #### Sparse Complete Sets for NP: Solution of a Conjecture by Berman and Hartmanis ﻿

(Cornell University, 1980-04)
In this paper we show that if NP has a sparse complete set under many-one reductions, then P=NP. The result is extended to show that if NP is sparse reducible, then P=NP. The main techniques of this paper generalize the ...