3
$\begingroup$

The class Co-NP is defined as all the languages $L$ such that $\overline{L} \in NP$. An example that appears in the book of Arora and Barak is of $\overline{SAT}$, which is defined as $\overline{SAT} = \{\phi : \phi \text{ is not satisfiable} \}$. My question is the following, given that $SAT$ corresponds to boolean functions represented with an alphabet (say $\{0,1\}$), then $\overline{SAT}$ should include bitstrings that correspond to non-satisfiable formulas but also butstrings that dont represent a valid boolean formula. Why is then in the book defiend as $\overline{SAT} = \{\phi : \phi \text{ is not satisfiable} \}$?

Shouldn't the definition be something like $\overline{SAT} = \{\phi : \phi \text{ is not satisfiable} \} \cup \{\phi : \phi \text{ does not encode a boolean formula} \}$.

$\endgroup$
7
$\begingroup$

Technically and formally, you are right. However, it is "nicer" to look at languages with sanitized input. And since detecting if the input does not describe a valid boolean formula is possible in polynomial time, it is sane. (Formally, you can polynomially reduce the books definition to yours and vice versa)

$\endgroup$
  • 2
    $\begingroup$ Indeed. Computational problems are almost always "promise problems", but we tend to ignore this in many cases because the promise is easily checkable in polynomial time - see section 1.1. in "On Promise Problems" by Oded Goldreich (wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf). $\endgroup$ – Rahul Savani Oct 29 '19 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.