8
$\begingroup$

I would like to know if the following NP-complete problem has a name and has been studied:

Input: Given a CNF formula $\varphi$ on $n$ variables, a truth assignment $\sigma:[n] \to \{T,F\}$ and an integer $k$;
Question: Can we transform $\sigma$ into a satisfying assignment for $\varphi$, swapping the truth values of at most $k$ pairs of variables.

It is very similar to the problem k-FLIP SAT (see my previous question for details); but here the number of truth values used cannot change.

In particular, I would like to know if there are some results about its parameterized complexity in the general case and under some restrictions (e.g. q-CNF formulas, max occurrences of a variable).

I did a few searches on google, but didn't find anything (but probably I'm not using the correct terms).

$\endgroup$
  • $\begingroup$ You may want to look at random k-SAT and phase transition litriture and the structure of the space of solutions. $\endgroup$ – Kaveh Mar 4 '16 at 14:36
  • $\begingroup$ E.g. see the work by Achlioptas and colleagues. If the clause ratio is in the hard section the closest solution to randomly selected assignment is $\Theta(n)$ far if I recall correctly. $\endgroup$ – Kaveh Mar 4 '16 at 14:38
  • 2
    $\begingroup$ I think it is W[1]-hard by a reduction from the parameterized 2-SAT problem.In this problem we are given a 2-SAT instance, and the goal is to find a satisfying assignment with at most k ones. $\endgroup$ – Igor Shinkar Mar 4 '16 at 15:21
  • 1
    $\begingroup$ Yes. For a Min-Ones-2-Sat instance, start from the all-0 assignment, add k dummy variables whose truth values do not affect the satisfiability of the formula, and set them to 1. $\endgroup$ – Serge Gaspers Mar 5 '16 at 13:39
  • $\begingroup$ @IgorShinkar: thanks! Meanwhile I found a W[1]-hardness reduction from independent set (that - I bet - is probably similar to the one used for Min-Ones-2-Sat). If you want convert the comment to an answer (the technique suggested by Serge is ok) but I'll wait to see is someone has a reference/known name for the problem. $\endgroup$ – Marzio De Biasi Mar 5 '16 at 18:50

Your Answer

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

Browse other questions tagged or ask your own question.