New answers tagged

0

Pick any unsatisfiable CNF SAT instance. Transform the CNF to 3-SAT. The new instance is an element of 3-co-SAT. Any unsatisfiable satisfiability instance undergoing the same 3-SAT CNF transformation is an example of 3-co-SAT.


0

The formula $$(x\vee y \vee z) \wedge (\overline{x}\vee y \vee z) \wedge(x\vee \overline{y} \vee z) \wedge(x\vee y \vee \overline{z}) \wedge(\overline{x}\vee \overline{y} \vee z) \wedge(\overline{x}\vee y \vee \overline{z}) \wedge(x\vee \overline{y} \vee \overline{z}) \wedge(\overline{x}\vee \overline{y} \vee \overline{z})$$ is in $3$-co-SAT.


3

If you have a fixed number of variables, then you have a fixed number of assignments $2^{|\text{vars}|}$, so there's a polynomial time algorithm for checking all possible assignments.


1

Let $\phi'$ be a SAT formula with $n$ variables. Consider the pair $(\phi, k)$ where $\phi$ is a formula with $2n$ variables that is obtained from $\phi'$ by adding $n$ new variables $x_1, \dots, x_n$ (if you want each new variable $x_i$ to appear in at least one clause you can add the trivial clause $(x_i \vee \overline{x}_i)$). $k=n$. If $\phi$ is ...


1

The correct answer is no. 3. Suppose $A \in \text{NP}$ and $A \notin \text{co-NP}$. Clearly this shows $\text{NP} \neq \text{coNP}$, but that's not a possible choice for this question. Observe that complement of the machine output can be trivially implemented in a deterministic polynomial machine. That is to say, $\text{P} = \text{co-P}$. Thus, if $\text{P} =...


Top 50 recent answers are included