En teoría de grafos y complejidad de circuitos , la función Tardos es un invariante de grafo introducido por Éva Tardos en 1988 que tiene las siguientes propiedades: [1] [2]
Para definir su función, Tardos utiliza un esquema de aproximación de tiempo polinomial para el número de Lovász, basado en el método del elipsoide y proporcionado por Grötschel, Lovász y Schrijver (1981). [3] Sin embargo, aproximar el número de Lovász del complemento y luego redondear la aproximación a un entero no produciría necesariamente una función monótona. Para que el resultado sea monótono, Tardos aproxima el número de Lovász del complemento a dentro de un error aditivo de , suma a la aproximación y luego redondea el resultado al entero más cercano. Aquí denota el número de aristas en el grafo dado y 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 camarilla 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 polinomial. Más tarde, la misma función se utilizó para proporcionar un contraejemplo a una supuesta prueba de P ≠ NP por Norbert Blum. [6]
