Polynomial terse sets

Let A be a set and k ∈ N be such that we wish to know the answers to x 1 ∈ A? , x 2 ∈ A? , …, x k ∈ A? for various k-tuples 〈x 1, x 2, …, x k 〉. 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, p-selective, p-generic sets, and the boolean hierarchy. In our framework unique satisfiability (and a variation of it called kSAT is, in some sense, “close” to satisfiability.

Authors

• Amihood Amir
• William I. Gasarch

Keywords

No keywords are indexed for this paper.