Now showing items 1-2 of 2

    • Computation Times of NP Sets of Different Densities 

      Hartmanis, Juris; Yesha, Yaacov (Cornell University, 1983-03)
      In this paper, we study the computational complexity of sets of different densities in NP. We show that the deterministic computation time for sets in NP can depend on their density if and only if there is a collapse or ...
    • String-Matching Cannot be Done by a Two-Head One-Way Deterministic Finite Automaton 

      Li, Ming; Yesha, Yaacov (Cornell University, 1983-10)
      We show that string-matching cannot be performed by a two-head one-way deterministic finite automaton (or even by a Turing machine with two one-way input heads and o(n) storage space). Thus we answer the special case ...