SAT Has No Wizards - Computer Science > Computational ComplexityReportar como inadecuado

SAT Has No Wizards - Computer Science > Computational Complexity - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.

Autor: Silvano Di Zenzo


Documentos relacionados