Now showing items 1-6 of 6

• #### Definability with Bounded Number of Bound Variables ﻿

(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 ﻿

(Cornell University, 1980-08)
NO ABSTRACT SUPPLIED
• #### Number of Quantifiers is Better than Number of Tape Cells ﻿

(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 ﻿

(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 ﻿

(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 ﻿

(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 ...