Mientras hojeaba publicaciones antiguas de CStheory.se , me encontré con una fascinante publicación de blog sobre el problema de la mortalidad matricial . A menos que haya malinterpretado el problema, establece que dada una colección finita de 3 x 3 matrices con entradas enteras para cada valor de matriz, uno debe decidir si existe un producto finito de esas matrices que sea igual a una matriz compuesta de todos los ceros.
Sorprendentemente, este problema es indecidible, debido a una reducción del problema de correspondencia posterior. Mi pregunta es: dada la indecidibilidad del problema y su vínculo con un problema relacionado con las máquinas de Turing, ¿puede demostrar que existe una manera de caracterizar (por ejemplo) todos los idiomas, la clase P y la clase NP usando matrices?
Yo mismo he trabajado un poco en esto, pero me falta el entrenamiento para asegurarme de que mi creencia sea correcta. Creo que este problema requeriría un poco de trabajo por parte del lector para resolverlo.
No sé cómo usar LaTeX para escribir matrices en SE, pero aquí está mi primer intento de caracterizar NP:
Dado un conjunto finito de 3 x 3 matrices con entradas enteras y un entero como una "consulta" NP, deje que una matriz adicional se tome como una "estructura". La "consulta" acepta la "estructura" si existe un producto de matrices de que equivale a una matriz que consta de solo ceros.M | M | k + k S
Este intento no está completo y no incluye ninguna prueba, como puede ver, pero quería reflexionar sobre el problema para ver si se podía hacer un intento más sofisticado para formalizar una noción de complejidad de la matriz. Esto es interesante porque, al igual que la caracterización de NP de Fagin usando la complejidad descriptiva, podría usarse para caracterizar NP de una manera independiente de la máquina.
fuente
Respuestas:
Esto no es una caracterización de NP: es solo un problema de NP completo (bueno, supongo que es NP completo, de todos modos). OK, si es así, podría caracterizar NP como la clase de problemas reducibles a su problema de matriz, pero ¿cómo va a definir las reducciones? El uso de reducciones de algún modelo de cómputo existente (por ejemplo, máquinas de Turing) sería contraproducente. ¿Qué ventajas tendría tal caracterización sobre, por ejemplo, considerar que NP es la clase de problemas reducible a, digamos, un conjunto independiente?
fuente