Polynomial Terse Sets (Extended Abstract)
Amihood Amir, William I. Gasarch · 1987
Let A be a set and k ∈ N be such that we wish to know the answers to x1∈ A?, χ2∈ A?, …, Xk∈ A? for various k-tuples (x1,x2, …,Xk)· If this problem requires k queries to A in order to be solved in polynomial time then A is called polynomial terse or pterse. We show the existence of both arbitrarily complex pterse and non-pterse sets; and that P=NP iff every NP-complete set is pterse. We also show connections with p-immunity, polynomial separability, p-generic sets, and the boolean hierarchy. Our techniques allow us to prove that Unique Satisfiability (USAT) is, in some sense, "close" to Satisfiability. In particular, we show that USAT is coNP-hard.