IJPAM: Volume 60, No. 2 (2010)
IBM Rome Scientific Center
University of Rome ``La Sapienza"
181, C. Colombo St., Rome, 00147, ITALY
e-mail: [email protected]
Abstract.We define various notions of structural independence of a decision problem. We then show that exhibits each of these properties. Using this result, we show that has no collective certificates of membership of the kind that we call ``wizards." As a consequence, all the programs that solve 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