SAT Has No Wizards - Computer Science > Computational ComplexityReport as inadecuate

SAT Has No Wizards - Computer Science > Computational Complexity - Download this document for free, or read online. Document in PDF available to download.

Abstract: An encoded decision problem is a pair E, F where E=words that encodeinstances of the problem, F=words to be accepted. We use -strings- in atechnical sense. With an NP problem E, F we associate the -logogram- of Frelative to E, which conveys structural information on E, F, and how F isembedded in E. The kernel KerP of a program P that solves E, F consists ofthose strings in the logogram that are used by P. There are relations betweenKerP and the complexity of P. We develop an application to SAT that reliesupon a property of internal independence of SAT. We show that SAT cannot havein its logogram strings serving as collective certificates. As consequence, allprograms that solve SAT have same kernel.

Author: Silvano Di Zenzo


Related documents