Función de Tardos contraejemplo al reclamo

En este hilo , la prueba de intentada por Norbet Blum se refuta sucintamente al señalar que la función de Tardos es un contraejemplo del Teorema 6. $P \neq NP$

Teorema 6 : Sea cualquier función booleana monótona. Suponga que hay un aproximador CNF-DNF que se puede usar para probar un límite inferior para . Entonces también se puede usar para probar el mismo límite inferior para . $f \in \mathcal{B}_n$ $\mathcal{A}$ $C_m(f)$ $\mathcal{A}$ $C_{st}(f)$

Aquí está mi problema: la función Tardos no es una función booleana, entonces, ¿cómo satisface las hipótesis del Teorema 6?

En este artículo , discuten la complejidad de la función , que en general no es una función booleana monótona, ya que aumentar los bordes puede hacer que más grande para hacer falso cuando era verdadero con menos 's en la entrada. La función no, en general, calcula en $\varphi(X) \leq f(v)$ $\varphi(X)$ $\varphi(X) \leq f(v)$ $1$ $\varphi(X) \geq f(v)$ $1$ y en . $T_1$ $0$ $T_0$

De hecho, los conjuntos de prueba y se eligen con precisión para que calcular en y en con monotonicidad signifique su función para calcular con precisión CLIQUE (definen el límite de los 'sy ' s en la red de entradas), por lo que estas observaciones implican que la función Tardos es la misma que CLIQUE, lo que claramente no es cierto. $T_1$ $T_0$ $1$ $T_1$ $0$ $T_0$ $1$ $0$

Sin embargo, muchas personas, y personas tan informadas, afirman que la función Tardos proporciona un contraejemplo inmediato, por lo que debe haber algo que me falta. ¿Podría por favor proporcionar una explicación detallada o prueba para aquellos de nosotros que somos partes interesadas pero no del todo a su nivel?

cc.complexity-theory np-hardness complexity-classes usuario144527
fuente

Una buena fuente sería el libro de Jukna , p.272 (justo antes del Teorema 9.28). Dada la función (no booleana)

, considere la función booleana

que es el umbral de

ϕ

$\phi$

f_{ϕ}

$f_\phi$

ϕ

$\phi$

se aplica el resultado.

f_{ϕ} (G) = {\begin{cases} 1 & if ϕ (G) \geq \sqrt{n} \\ 0 & otherwise \end{cases}

$f_\phi(G) = \begin{cases} 1 & \text{if } \phi(G) \geq \sqrt{n}\\ 0&\text {otherwise}\end{cases}$

Clement C.

Entonces, para ser claros, me estás diciendo que

se evaluará a

en camarillas de tamaño

f_{ϕ} (G)

$f_\phi(G)$

1

$1$

en los gráficos de

vértices inducidos por adecuada

\sqrt{n}

$\sqrt{n}$

0

$0$

n

$n$

colorantes?

⌊ \sqrt{n} - 1 ⌋

$\lfloor \sqrt{n}-1 \rfloor$

user144527

Por supuesto, esto no se cumple para ningún

. Pero la función de Tardos

se basa en una función de gráfico monótono

satisface

. Entonces, el umbral

hace exactamente lo que usted dice. Vea el final de la Sección 9.8 aquí .

ϕ

$\phi$

f_{ϕ}

$f_{\phi}$

ϕ

$\phi$

ω (G) \leq ϕ (G) \leq χ (G)

$\omega(G)\leq \phi(G)\leq \chi(G)$

f_{ϕ}

$f_{\phi}$

ϕ

$\phi$

Stasys

Correcto. Por cierto, en realidad no entiendo por qué las personas votan negativamente su pregunta (elegible en vista de todo este ruido en torno a esta "prueba"). Ahora es el autor de este giro de reclamo P! = NP: explique por qué la "prueba" NO funcionará para la función de Tardos. Señale la página X y la (s) línea (s) Y en el papel. Sugerencia: el error estará en el límite superior de la cantidad de errores introducidos durante la aproximación (las negaciones pueden aniquilar muchos términos previamente "válidos"). De lo contrario (sin explicación) = no "prueba".

Stasys

@Stasys, tu primer comentario puede ser una respuesta.

Kaveh

Respuestas:

entonces estas observaciones implican que la función Tardos es la misma que CLIQUE. $f$

Respuesta corta: NO.

Es solo un monótono "como una camarilla": acepta todas las cliques, y rechaza todos los gráficos completos -partitos. Sin embargo, puede aceptar algunos gráficos rechazados por CLIQUE: gráficos con pero (los llamados gráficos "no perfectos"). El artículo de Grötschel, Lovász y Schrijver implica que tiene un circuito no monótono de tamaño polinómico. Pero, de acuerdo con el Teorema 6 en la "prueba" , cualquier $k$ $(k-1)$ $G$ $\omega(G) < k$ $\chi(G)\geq k$ $f$ La función booleana monótona similar a una camarilla requiere circuitos no monótonos de tamaño superpolinomial. Entonces, uno de estos dos documentos debe estar equivocado. El documento GLS-1981 ya tenía más de 35 años ...

Lo que hace Tardos es lo siguiente. Ella parte de la función gráfica , donde es la famosa función theta de Lovász. El hecho fundamental es que el número encuentra entre el número de camarilla y el número cromático: . Luego usa el hecho de que $\varphi(G):=\vartheta(\overline{G})$ $\vartheta$ $\varphi(G)$ $\omega(G)\leq \varphi(G)\leq \chi(G)$ $\vartheta(G)$ se puede aproximar en tiempo polinómico. En base a esto, ella define una función gráfica con las siguientes propiedades: $\phi(G)$

Los valores de se pueden calcular en tiempo polinómico (en el número de vértices). $\phi(G)$ $n$
es monótono: agregar bordes solo puede aumentar su valor. $\phi$
se mantiene para todos los gráficos . $\omega(G)\leq \phi(G)\leq \chi(G)$ $G$

Luego (como señala Clement C.) define la función booleana monótona deseada como: iff . Por (1), la función tiene un circuito (no monótono) de tamaño polinómico. Por (2), es una función booleana monótona. Por (3), acepta todas las cliques, y rechaza todos los gráficos completos -partitos. $f$ $f(G)=1$ $\phi(G)\geq k$ $f$ $f$ $k$ $(k-1)$

Ver aquí para detalles técnicos.

Stasys
fuente

El documento GLS-1981 está aquí gratis. Este documento, a su vez, se basa en el papel elipsoide Khachiyan-1979. Entonces, (al menos) uno de estos tres documentos debe estar equivocado?

Tobias Müller

@Tobias: bueno, estamos bastante seguros de que estos dos> 35 documentos antiguos son correctos (muchas veces reproducidos en conferencias, alguien ya habría observado un error). El problema con la "prueba" actual es que es "por construcción", no "por un argumento" (como en los dos documentos mencionados). Entonces se considera difícil señalar un lugar específico , donde la "construcción" falla. Especialmente cuando la "construcción" es tan imprecisa. Es por esto que creo que ahora es el deber del autor, no de nosotros, hasta el punto de que este lugar (donde Tardos no pasa por su construcción.)

Stasys