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:
- Chose a random variable from the CNF (call it R1)
- Negate the CNF expression
- Convert the negated expression in step 2 back to CNF format
- Create a list and in every even index place (R1 || !R1), and in the odd index place the clauses from step 3.
- 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).