algorithmnpreductionnp-completenp-hard

Strategy for reducing CNF-SAT to this problem


Suppose there is a satisfiability problem (call it oscillating-CNF) where the input is a list of CNF clauses and we want to show that this problem is indeed NP-complete (by reducing CNF-SAT to oscillating-CNF). A satisfied oscillating-CNF instance is when each even indexed clause (0-2-4) is true and each uneven indexed clause is false (1-3-5...).

My question is this, is it a feasible strategy to:

  1. Chose a random variable from the CNF (call it R1)
  2. Negate the CNF expression
  3. Convert the negated expression in step 2 back to CNF format
  4. Create a list and in every even index place (R1 || !R1), and in the odd index place the clauses from step 3.
  5. use this list as input to the oscillating-CNF problem

Solution

  • The problem is, when you negate a disjunctive clause it becomes a conjunction. I would keep the original problem in the even clauses, and introduce auxiliary variables for the odd clauses (making them trivially dissatisfiable without containing the original variables).