P vs. NP - Abstracciones Exponenciales

Aplicación de las abstracciones exponenciales a los problemas HC & TSP

Compra en Amazon la versión en papel.
Compra en Google la versión en digital.

Portada

P versus NP Diseño de Algortimos Estructuras de datos Problemas Intratables Hamiltonian Circuit problem (HC) Travelling salesman problem (TSP)

Sinopsis

Desde 2019, de forma independiente, hemos estado explorando e investigando nuevas formas de diseñar algoritmos polinómicos para los problemas que rodean uno de los siete problemas del milenio: el reto P vs. NP.

Con nuestro trabajo, proponemos una metodología de diseño alternativa a la matemática, basada en el uso de las abstracciones exponenciales y fundamentada, tanto teórica como físicamente, en el uso de la abstracción como un recurso computacional adicional al espacio y al tiempo. Con esta metodología, buscaremos diseñar algoritmos que sean polinómicos a pesar de que trabajen de forma abstracta con una información que, para nosotros, tenga un valor que potencialmente crezca en términos exponenciales.

A lo largo de este libro, al mismo tiempo que presentamos nuestro trabajo de investigación, abordaremos paso a paso, de forma práctica y didáctica, el diseño de un algoritmo prototipo que será polinómico para HC y pseudopolinómico para TSP. Esto nos valdrá de apoyo para argumentar cómo, gracias a la dimensión de lo abstracto, podemos evitar que, físicamente, nuestros algoritmos (y máquinas de cómputos) tengan que enfrentarse de forma directa a la naturaleza exponencial de los problemas. Si bien hemos dejado fuera del alcance de nuestra investigación la verificación formal de estos, entendemos que son lo suficientemente correctos como para permitirnos constatar de forma práctica la viabilidad de la metodología que proponemos con nuestra investigación.

Preguntas clave de la investigación

  1. ¿Podría ser la abstracción la puerta que nos permita resolver la conjetura P vs. NP a favor de que NP sea igual a P?
  2. ¿Podemos representar la entrada de un algoritmo utilizando un espacio polinómico respecto de N a pesar de que esta entrada tenga un poder de abstracción exponencial?
  3. ¿Podemos representar la salida de un algoritmo utilizando un espacio polinomial a pesar de que esta salida tenga un poder de abstracción exponencial?
  4. ¿Podemos diseñar un algoritmo eficiente para los problemas HC y TSP usando Φ como la idea abstracta del conjunto solución de Tours?
  5. ¿Seríamos capaces de representar una salida con el conjunto de todos los Tours solución (es decir, Φ) siguiendo un crecimiento espacial polinomial?
  6. ¿Seríamos capaces de construir Φ en tiempo polinómico?
  7. ¿Seríamos capaces de leer un Tour T solución del conjunto Φ, usando un algoritmo polinómico?

Índice

  1. Diagnóstico
    1. Space vs Time
      1. Hipótesis: Space Bombe
      2. La recursividad como un antipatrón de diseño
    2. La Naturaleza de Los Problemas
      1. De los problemas a los algoritmos
      2. De las instancias, a las respuestas
      3. Complejidad del conjunto de muestras
      4. Nuestra aliada, la matemática
    3. Los límites físicos
  2. La abstracción aplicada al diseño de algoritmos
    1. El poder de las abstracciones
    2. El poder de los símbolos
    3. La abstracción como recurso computacional
    4. La abstracción como puerta hacia P = NP
    5. Explorando el diseño de abstracciones
    6. Rediseño
      1. Reducciónde SETHC a HC
      2. Explorando nuestros límites
      3. Visión general del nuevo diseño
    7. Exponential Abstract DataType (EADT)
      1. Programming with Abstract Data Types
      2. Extendiendo la metodología ADT hacia EADT
  3. Diseño del algoritmo
    1. TSP Machine
    2. Explorando las estructuras recursivas frente a los desequilibrios exponenciales
      1. Mecanismos de control exponencial
      2. Legibilidad de estructuras de datos exponenciales
    3. Explorando disruptivos enfoques del diseño general de los algoritmos
    4. TSP Machine usando el conjunto Phi
    5. Introducción a PathSet
    6. Hacia el Diseño Final
      1. Timeline
      2. Lazy Building
      3. Actions Database
      4. Divide, divide, y vencerás
  4. Graph PathSet
    1. UP and JOIN
    2. Eliminación de nodos
    3. Superposición de Rutas
      1. Lectura anticipada
      2. Rediseño Continuo
    4. Sistema de Owners
      1. Reglas Básicas
      2. Reglas de Colores
    5. Proceso de Lectura
  5. Prototype
    1. Hamiltonian Machine
      1. Constructor
      2. Send to destines
      3. Execution Pipeline
      4. Getters
    2. Program(Grafo)
    3. Timeline
      1. Constructor
      2. Cells's Table:Construction
      3. Reading cells
      4. Pushing parents
      5. Reading Line
      6. Executing cells
      7. Removing cells
    4. Actions
      1. DBActions & Actions
      2. Execution
    5. GraphPathSet Components
      1. NodeId
      2. Node
      3. Edge
      4. Owners
    6. GraphPathSet
      1. PathSet Initialization
      2. Adding Nodes
      3. UP
      4. Deleting
      5. Deleting Node
      6. Owners Review
      7. JOIN
      8. Getters
    7. Reader
      1. Constructor
      2. Reading
      3. Selection
      4. Reducing
      5. Reading Tour
      6. Reader for Testing
      7. PathSet ExpReader
    8. Travelling Salesman Machine
  6. Testing Prototype
    1. Instancia del dodecaedro
    2. Hamiltonian Graph Detection Test
    3. TSP Optimal Set Test
  7. Complexity Prototype
    1. Agile Asymptotic Analysis
    2. Análisis experimental
    3. Rediseño
  8. Conclusiones
    1. Redefinición del problema
    2. Abstracciones exponenciales vs. Space Boom
    3. La libertad de cuestionarnos
A. Recursos Adicionales
Bibliografía

Libros de referencia

Garey, M.R. and D.S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman. isbn: 9780716710448
Arora, S. and B. Barak (2017). Computational Complexity: A Modern Approach. Cambridge University Press. isbn: 9781316612156
Savage, J.E. (1998). Models of Computation: Exploring the Power of Computing. Addison-Wesley. isbn: 9780201895391
Nielsen, M.A. and I.L. Chuang (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press. isbn: 9781107002173