¿Es correcto el algoritmo de la camarilla de Ashay Dharwadker?

Question

Cuando escribes "algoritmo de camarilla" en Google www.dharwadker.org/clique/ aparece como un segundo resultado. Cita del resumen:

Presentamos un nuevo algoritmo polinomio-tiempo para encontrar las máximas cliques en los gráficos. (...) El algoritmo encuentra una camarilla máxima en todos los ejemplos conocidos de gráficos . Dada la importancia de la pregunta P versus NP, preguntamos si existe un gráfico para el que el algoritmo no pueda encontrar una camarilla máxima.

En el 4.4 está escrito:

Dado un simple gráfico G con n vértices, el algoritmo toma menos de $n^8+2n^7+n^6+n^5+n^4+n^3+n^2$ pasos para terminar.

Así que Dharwadker encontró un algoritmo que resuelve el problema de NP en tiempo P... Esto significaría que P = NP ...

Bueno, no estoy seguro... Mi suposición es que el algoritmo de Dharwadker no es correcto, es decir, para algún gráfico de entrada, el algoritmo no funcionará. Es por eso que él está presentando sólo "todos los ejemplos conocidos de gráficos" ...para lo cual obviamente su algoritmo está funcionando...

¿Dharwadker tiene razón y tenemos una prueba de que P = NP? ¿O puedes presentar un contra-ejemplo para su algoritmo?

Answer 1

Este algoritmo no es correcto.

(Actualizado)

http://pastebin.com/KTqSgryK

Pega ese archivo como grapt.txt para la aplicación Dharwadker - no encontrará que los primeros 5 vértices comprenden una camarilla. Este es un ejemplo del llamado algoritmo codicioso que puede encontrar rápidamente una solución bastante buena para muchas condiciones de arranque, pero su codicia puede llevarlo a una trampa.

Answer 2

Dudo que sea correcto. Su perfil nos dice que además de encontrar un algoritmo de tiempo polinomial para las máximas camarillas en los gráficos, también ha conectado el teorema de cuatro colores al Modelo Estándar en la física y ha predicho Higgs-Boson a partir del teorema de cuatro colores, además de calcular la constante cosmológica de Einstein en su tiempo libre:

http://www.dharwadker.org/profile.html

Afirma ser el fundador y director del Instituto de Matemáticas de Gurgaon (India). Siendo un indio, puedo decir que nunca he oído hablar de este instituto. Lo más probable es que sea un matemático aficionado.

Answer 3

De la introducción del periódico (no lo he leído y probablemente no lo leeré todo):

Probamos que cada gráfico con n vértices y grado mínimo de vértice $ \delta $ debe tener una camarilla máxima de tamaño al menos $ \lceil \frac n{n− \delta } \rceil $ y que el algoritmo siempre encontrará una camarilla de al menos este tamaño.

Esta parece ser una afirmación razonable. En realidad no resuelve el problema de las camarillas, ya que sólo encuentra "grandes" camarillas en un sentido específico. Sin embargo, parece estar más interesado en la conexión de la teoría de Ramsey:

Además, demostramos que esta condición es la mejor posible en términos de $n$ y $ \delta $ construyendo explícitamente gráficos para los cuales el tamaño de una camarilla máxima es exactamente $ \lceil \frac n{n− \delta } \rceil $

Pensé que podría estar malinterpretando la pregunta real, ya que encontrar un límite inferior en las camarillas máximas y luego demostrar que es un límite superior en algunos gráficos no es suficiente para resolver el problema de las camarillas. Pero luego escribe:

En la sección 7, demostramos el algoritmo encontrando camarillas máximas para varios EJEMPLOS de gráficos famosos, incluyendo dos grandes gráficos de referencia con camarillas máximas ocultas.

lo que parece indicar que admite que su algoritmo no encuentra camarillas máximas en todas las circunstancias.

Mi juicio: No lo descartaría de plano, el autor no es obviamente un maniático, el algoritmo puede ser correcto e incluso interesante, pero no resuelve P=NP.