Now showing items 1-6 of 6

    • Definability with Bounded Number of Bound Variables 

      Immerman, Neil; Kozen, Dexter (Cornell University, 1987-03)
      A theory satisfies the $k$-variable-property if every first-order formula is equivalent to a formula with at most $k$ bound variables (possibly reused). Gabbay has shown that a fixed time structure satisfies the $k$-variable ...
    • First Order Expressibility as a New Complexity Measure 

      Immerman, Neil (Cornell University, 1980-08)
    • Number of Quantifiers is Better than Number of Tape Cells 

      Immerman, Neil (Cornell University, 1980-02)
      We introduce a new complexity measure, $QN[f(n)]$, which clocks the size of sentences from predicate calculus needed to express a given property. Techniques from logic are used to prove sharp lower bounds in the measure. ...
    • On Complete Problems for NP$\cap$CoNP 

      Hartmanis, Juris; Immerman, Neil (Cornell University, 1985-04)
      It is not known whether complete languages exist for $NP\cap CoNP$, and Sipser has shown that there are relativizations so that $NP\cap CoNP$ has no $\leq ^{P}_{m}$-complete languages. In this paper we show that $NP\cap ...
    • One-Way Log-Tape Reductions 

      Hartmanis, Juris; Immerman, Neil; Mahaney, Stephen R. (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 Sets in NP-P: EXPTIME Versus NEXPTIME 

      Hartmanis, Juris; Sewelson, Vivian; Immerman, Neil (Cornell University, 1983-02)
      This paper investigates the structural properties of sets in NP-P and shows that the computational difficulty of lower density sets in NP depends explicitly on the relations between higher deterministic and nondeterministic ...