# Is this restricted promise-3SAT version coNPComplete?

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)?

• Can you formulate your problem precisely? How do you encode the property? Jul 2 '17 at 10:24
• 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) Jul 2 '17 at 10:50
• 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. Jul 2 '17 at 10:57
• 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. Jul 2 '17 at 10:59
• Perhaps you could update your post with a formal statement of your problem. Jul 2 '17 at 11:23

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.