Polynomial Terse Sets (Extended Abstract)
- 1 June 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Let A be a set and k ∈ N be such that we wish to know the answers to x 1 ∈ A?, χ 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, 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.Keywords
This publication has 0 references indexed in Scilit: