New answers tagged np
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