**Authors:** Richard Beigel

**Abstract:**
A set *A* is p-terse (p-superterse) if, for all *q*, it is
not possible to answer *q* queries to *A* by making only
*q* - 1*A* (any set
*X*). Formally, let FP_{q-tt}^{A}
be the class of functions reducible to *A* via a polynomial-time
truth-table reduction of norm *q*, and let
FP_{q-T}^{A} be the class of functions
reducible to *A* via a polynomial-time Turing reduction that
makes at most *q* queries. A set *A* is *p-terse* if
FP_{q-tt}^{A} is not contained in
_{(q-1)-T}^{A}*q*. *A* is *p-superterse* if
FP_{q-tt}^{A} is not contained in
_{(q-1)-T}^{X}*q* and sets *X*.

We show that all NP-hard sets (under
≤^{p}_{tt}-reductions) are p-superterse, unless it
is possible to distinguish uniquely satisfiable formulas from
satisfiable formulas in polynomial time. Consequently, all
NP-complete sets are p-superterse unless P = UP (one-way functions
fail to exist), R = NP (there exist randomized polynomial-time
algorithms for all problems in NP), and the polynomial-time hierarchy
collapses. This mostly solves the main open question of Amir &
Gasarch (Structures '87).

Allowing the number of queries *q* to be a function of the input
length *n*, we obtain nontrivial partial answers to a question posed
by Krentel: Namely, for all NP-complete sets *A* and all sets
*X*,

Finally, we define pbtt-cylinders, a natural class that includes all
≤^{p}_{m}-complete sets for NP, PSPACE, and
exponential time. For pbtt-cylinders, we show that p-terseness is
equivalent to p-superterseness. We also prove a translational lemma
for non-p-terse sets; this allows us to extend the preceding result to
≤^{p}_{btt}-complete sets for NP, PSPACE, and
exponential time.