It is easy to verify that a syntactic symmetry of a CNF formula is correct.

Is it also possible to check in polynomial time that a semantic symmetry which is not a syntactic symmetry of a formula is correct?

What is the complexity of the problem of checking the validity of a CNF formula's semantic symmetry?

Note that a syntactic (resp. semantic) symmetry $\sigma$ of a CNF formula $F$ is a permutation of its literals such that for all literal $x$, $\sigma(\neg x)=\neg \sigma(x)$ and $\sigma(F) = F$ (resp. $\sigma(F) \equiv F$).

  • 2
    $\begingroup$ It’s coNP-complete under ctt-reductions (and likely under many-one reductions as well). $\endgroup$ – Emil Jeřábek Sep 19 '18 at 15:08
  • $\begingroup$ @EmilJeřábek what are ctt-reductions? $\endgroup$ – RTK Sep 19 '18 at 16:13
  • 2
    $\begingroup$ Conjunctive truth-table reductions. In this case, it is enough to take the conjuction of two queries. $\endgroup$ – Emil Jeřábek Sep 19 '18 at 16:26
  • $\begingroup$ I found this post on ctt-reductions (cstheory.stackexchange.com/questions/39858/…) but it doesn't help me understanding how to proceed with the reduction. Please do you have any reference that could help me to first understand conjunctive truth-table reductions and then to show the coNP-completeness of the problem? $\endgroup$ – RTK Sep 19 '18 at 16:45
  • 1
    $\begingroup$ Oh, you mean that your permutations can actually negate variables? Then yes, but the symmetry group is $C_2\wr S_n$, I would have to think if it’s still generated by $2$ elements. $\endgroup$ – Emil Jeřábek Sep 19 '18 at 17:38

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.