Given a $3SAT$ problem the decision version of the problem (if it has a solution or not) is $NPComplete$. Now, given that we consider the promise version of the $3SAT$ problem, the promise is every $3SAT$ problem provided always has at least 1 solution.

Query: Does every solution of the above $3SAT$ problem instance have a particular property (one that can be tested in polynomial time. For eg: 'for any solution $A_i$, $N$ numbers immediately smaller than A are co-prime' or something similar; where $N$ is the input length)?

The problem and property can be encoded as a pair consisting of $3SAT$, and another $N$ input circuit of polynomial size ($N^c$ for some constant $c$)

This promise version is definitely in $co-NP$ (as if there is a solution that does not satisfy the given property, that solution is the $co-NP$ certifcate of polynomial length).

Is this problem also $co-NPComplete$ (as it still involves getting the failing solution first)?

  • $\begingroup$ Can you formulate your problem precisely? How do you encode the property? $\endgroup$ Commented Jul 2, 2017 at 10:24
  • $\begingroup$ If we have an Algorithm that tests the given property, the running time of the Algorithm on a DTM would be polynomial/bounded w.r.t. to the bits in the input size. Thus, I was assuming we can always have a polynomial sized circuit that tests the same. (I assumed that was the query regarding encoding) $\endgroup$
    – J.Doe
    Commented Jul 2, 2017 at 10:50
  • 1
    $\begingroup$ How does an instance of your problem look? A pair consisting of a CNF on $n$ variables and a circuit on $n$ inputs? Note that "polynomial size" circuit doesn't quite make sense - you need to fix the polynomial. For every polynomial you can have a different variant of your problem. Alternatively, the circuit can be unrestricted - the problem only becomes easier. $\endgroup$ Commented Jul 2, 2017 at 10:57
  • $\begingroup$ Given a CNF and a solution, it is NP-complete to ask whether there is another solution (if I remember correctly). This involves a reduction which plants a specific solution. If your property is "all solutions are the planted solution", then you get a coNP-complete problem. $\endgroup$ Commented Jul 2, 2017 at 10:59
  • 1
    $\begingroup$ Perhaps you could update your post with a formal statement of your problem. $\endgroup$ Commented Jul 2, 2017 at 11:23

1 Answer 1


Your problem is coNP-complete when the property is "all variables are zero". Given a SAT formula $\varphi$ on $x_1,\ldots,x_n$, construct a new SAT formula $\psi$ by replacing each clause $C$ of $\varphi$ with $\lnot y \lor C$ (where $y$ is a new variable), and adding clauses $y \lor \lnot x_i$ for $1 \leq i \leq n$. The satisfying assignments of $\psi$ are obtained from those of $\psi$ by setting $y = 1$, and there is an additional satisfying assignment in which all variables are zero. Hence $\varphi$ is satisfiable iff not all satisfying assignments of $\psi$ satisfy the property.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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