Reduction-Based MAX-3SAT with Low Nonlinearity and Lattices Under Recombination

A new construction is introduced for creating random MAX-3SAT instances with low nonlinearity. Instead of generating random clauses, we generate random SAT expressions over 3 variables and then convert these into CNF SAT clauses. We prove that this yields structured problems with much lower nonlinearity. We also introduce a new method for weighting MAX-SAT clauses that preserves low nonlinearity and also breaks up plateaus. We evaluate these new problems by enumeration of instances with \(n = 30\) variables. One unexpected result is that Partition Crossover creates more tunnels on these semi-structured MAX-SAT problems compared to results on random NK landscapes. We show that Partition Crossover induces hypercube lattices over subsets of local optima; all of the local optima which appear in a lattice can be evaluated with a single linear equation.