NP-hard Sets are P-Superterse Unless R = NP

Title: NP-hard Sets are P-Superterse Unless R = NP

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 queries to 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 FP_(q-1)-T^A for all constants q. A is p-superterse if FP_q-tt^A is not contained in FP_(q-1)-T^X for all constants 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,

FP_q(n)-tt^A is not contained in FP_(q(n)-1)-T^X unless SAT is in RTIME(n^O(q(n))) This is interesting whenever q(n) = o(n/logn). As a special case, FP_logⁱn-tt^A is not contained in FP_{(logⁱn-1)-T}^X unless RTIME(n^polylogn) = NTIME(n^polylogn) We extend the preceding results to tt-helpers; this allows us to isolate the key properties of NP-complete sets used in the proofs.

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.

Download Full Paper