Función de Tardos

En teoría de grafos y en complejidad de circuitos, la función de Tardos es un invariante de un grafo introducido por Éva Tardos en 1988.^[1]​^[2]​

La función de Tardos posee las siguientes propiedades:^[1]​

• Al igual que el número de Lovász del complemento de un grafo, la función de Tardos se encuentra entre el número de clique y el número cromático del grafo. Ambos números son NP-difíciles de calcular.
• La función de Tardos es monótona, en el sentido de que añadir aristas a un grafo solo puede hacer que su función de Tardos aumente o se mantenga constante, pero nunca disminuya.
• La función de Tardos se puede calcular en tiempo polinómico.
• Cualquier circuito monótono para calcular la función de Tardos requiere un tamaño exponencial.

Para definir su función, Tardos utiliza el esquema de aproximación de tiempo polinómico para el número de Lovász, basado en el método del elipsoide y proporcionado por Grötschel, Lovász y Schrijver (1981). Sin embargo,^[3]​ aproximar el número de Lovász del complemento y redondear la aproximación a un entero no necesariamente produciría una función monótona. Para que el resultado sea monótono, Tardos aproxima el número de Lovász del complemento con un margen de error aditivo de ${\displaystyle 1/n^{2}}$, suma ${\displaystyle m/n^{2}}$ a la aproximación y redondea el resultado al entero más cercano. Aquí, ${\displaystyle m}$ denota el número de aristas del grafo dado y ${\displaystyle n}$ denota el número de vértices.^[1]​

Tardos utilizó su función para demostrar una separación exponencial entre las capacidades de los circuitos lógicos booleanos monótonos y los circuitos arbitrarios.

Un resultado de Alexander Razborov, utilizado previamente para demostrar que el número de clique requería circuitos monótonos exponencialmente grandes,^[4]​^[5]​ también muestra que la función de Tardos requiere circuitos monótonos exponencialmente grandes a pesar de ser computable por un circuito no monótono de tamaño polinómico.

Posteriormente, la misma función se utilizó para proporcionar un contraejemplo a una supuesta demostración de P ≠ NP planteada por Norbert Blum.^[6]​