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$ Jul 2 '17 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
    Jul 2 '17 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$ Jul 2 '17 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$ Jul 2 '17 at 10:59
  • 1
    $\begingroup$ Perhaps you could update your post with a formal statement of your problem. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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