<p>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)</p>

CC BY-SA 4.0
2019-10-29T20:05:19.400Z
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 (http://www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf).
Rahul Savani
CC BY-SA 4.0
2019-10-27T22:22:04.430Z
2019-10-27T22:22:04.430Z
Daniel
<p>The class Co-NP is defined as all the languages <span class="math-container">$L$</span> such that <span class="math-container">$\overline{L} \in NP$</span>. An example that appears in the book of Arora and Barak is of <span class="math-container">$\overline{SAT}$</span>, which is defined as <span class="math-container">$\overline{SAT} = \{\phi : \phi \text{ is not satisfiable} \}$</span>. My question is the following, given that <span class="math-container">$SAT$</span> corresponds to boolean functions represented with an alphabet (say <span class="math-container">$\{0,1\}$</span>), then <span class="math-container">$\overline{SAT}$</span> 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 <span class="math-container">$\overline{SAT} = \{\phi : \phi \text{ is not satisfiable} \}$</span>? </p>

<p>Shouldn't the definition be something like <span class="math-container">$\overline{SAT} = \{\phi : \phi \text{ is not satisfiable} \} \cup \{\phi : \phi \text{ does not encode a boolean formula} \}$</span>.  </p>

<complexity-classes>
Co-NP definition
Apo
# Co-NP definition

(Asked by: username_0 on 2019-10-27)

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} \}$.

**Tags:** complexity-classes


---

## 1 answers

### Answer by username_1 on 2019-10-27. Score: 7 | Accepted answer

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)

> **Comments:**
> **username_2**: 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 (http://www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf).  

---

