JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing by Author "Fortune, Steven"
Now showing items 16 of 6

The Complexity of Equivalence and Containment for Free Single Variable Program Schemes
Fortune, Steven; Hopcroft, John E.; Schmidt, Erik Meineche (Cornell University, 197705)Noncontainment for free single variable program schemes is shown to be NPcomplete. A polynomial time algorithm for deciding equivalence of two free schemes, provided one of them has the predicates appearing in the same ... 
A Note on Cryptography and NP$\cap$ CoNPP
Brassard, Giles; Fortune, Steven; Hopcroft, John E. (Cornell University, 197804)Diffie and Hellman [2] propose the use of the exponential function in a finite field for cryptographic purposes. The proposal is based on the conjecture that the inverse function, the logarithm, is not feasibly computable. ... 
A Note on Rabin's NearestNeighbor Algorithm
Fortune, Steven; Hopcroft, John E. (Cornell University, 197804)Rabin has proposed a probabilistic algorithm for finding the closest pair of a set of points in Euclidean space. His algorithm is asymtomatically linear whereas the best of the known deterministic algorithms take order ... 
A Note on the Sparse Complete Sets
Fortune, Steven (Cornell University, 197810)Hartmanis and Berman have conjectured that all NPcomplete sets are polynomial time isomorphic. A consequence of the conjecture is that there are no sparse NPcomplete sets. We show that the existence of an NPcomplete ... 
Parallelism in Random Access Machines
Fortune, Steven; Wyllie, James C. (Cornell University, 197801)A model of computation based on random access machines operating in parallel and sharing a common memory is presented. The computational power of this model is related to that of traditional models. In particular, ... 
Sorting Helps for Voronoi Diagrams
Chew, L. Paul; Fortune, Steven (Cornell University, 199305)It is well known that, using standard models of computation, it requires $\Omega(n$ log $n$) time to build a Voronoi diagram for $n$ data points. This follows from the fact that a Voronoi diagram algorithm can be used ...