Now showing items 1-6 of 6

    • The Complexity of Equivalence and Containment for Free Single Variable Program Schemes 

      Fortune, Steven; Hopcroft, John E.; Schmidt, Erik Meineche (Cornell University, 1977-05)
      Non-containment for free single variable program schemes is shown to be NP-complete. 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$ CoNP-P 

      Brassard, Giles; Fortune, Steven; Hopcroft, John E. (Cornell University, 1978-04)
      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 Nearest-Neighbor Algorithm 

      Fortune, Steven; Hopcroft, John E. (Cornell University, 1978-04)
      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, 1978-10)
      Hartmanis and Berman have conjectured that all NP-complete sets are polynomial time isomorphic. A consequence of the conjecture is that there are no sparse NP-complete sets. We show that the existence of an NP-complete ...
    • Parallelism in Random Access Machines 

      Fortune, Steven; Wyllie, James C. (Cornell University, 1978-01)
      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, 1993-05)
      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 ...