IJPAM: Volume 60, No. 2 (2010)

ON THE STRUCTURE OF BOOLEAN SATISFIABILITY

Silvano Di Zenzo
IBM Rome Scientific Center
University of Rome ``La Sapienza"
181, C. Colombo St., Rome, 00147, ITALY
e-mail: silvano.dizenzo@acm.org


Abstract.We define various notions of structural independence of a decision problem. We then show that $SAT$ exhibits each of these properties. Using this result, we show that $SAT$ has no collective certificates of membership of the kind that we call ``wizards." As a consequence, all the programs $P$ that solve $SAT$ have the same ``kernel."

Received: February 15, 2010

AMS Subject Classification: 68Q15

Key Words and Phrases: NP problems, certificates of membership, structural independence, witness, wizard, logogram, program kernel, irreducible kernel

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2010
Volume: 60
Issue: 2