2002 NAAS/AJAS Meeting in Boston
Left to right: David Hsi, NAAS/AAAS/SWARM Delegate; Lynn Brandvold, NMJAS Director; and Tom Widland, 2001 Paper Competition Winner
The Effects of Reductions on the Difficulty Topology of the SAT Problem
Thomas Widland
Albuquerque Academy, Albuquerque, NM
Abstract
The "difficulty topology" of a problem is the manner in which difficulty varies with changes in the parameters of the problem. For SAT problems of similar structure, we find an exponential relationship between the difficulty before and after our reduction, which introduces a linear increase in the length of the inputs. We show that the reduction reduces the difficulties of formulas relative to others of the same length and make conjectures based on this result.
Back to NMAS home page
Lynn Brandvold
last modified: 05-01-2002