En las pruebas de propiedades de gráficos, un algoritmo consulta un gráfico de destino para detectar la presencia o ausencia de aristas y necesita determinar si el objetivo tiene una determinada propiedad o está lejos de tener la propiedad. (Se puede pedir que un algoritmo tenga éxito con un error de 1 cara o de 2 caras). Un gráfico es lejos de tener una propiedad si no se pueden agregar / restar bordes para hacerlo Tener la propiedad.
Se dice que una propiedad es comprobable si se puede probar de la manera especificada anteriormente en un número sub-lineal de consultas, o mejor aún, en un número de consultas independientes de (pero no ). La noción de qué propiedades son también se puede formalizar, pero debe quedar claro.
Hay muchos resultados que caracterizan qué propiedades son comprobables, con muchos ejemplos de propiedades comprobables naturales. Sin embargo, no conozco muchas propiedades naturales que se sabe que no son comprobables (digamos en un número constante de consultas), una de las que estoy familiarizado es la prueba de isomorfismo en un gráfico dado.
Entonces, mi pregunta es: ¿qué propiedades gráficas naturales se sabe que no son comprobables?
Respuestas:
En el modelo de matriz de adyacencia, hay un límite inferior de en la complejidad de la consulta de probar si un gráfico de vértices consiste en dos copias isomórficas de algún gráfico de -vertex (vea Introducción a las propiedades del gráfico de prueba - Goldreich para una encuesta).Ω ( n ) norte n / 2
Además, hay muchos límites inferiores que dependen de para los probadores con error unilateral, por ejemplo: testing -Clique, -Cut y -Bisection (consulte Prueba de propiedades y su conexión con el aprendizaje y la aproximación - Goldreich Goldwasser, Ron )norte ρ ρ ρ
Además, en el modelo de gráfico de grado acotado, la prueba de 3-Colorability requiere consultas , mientras que la prueba de 2-Colorability (es decir, Bipartiteness) requiere (ver Prueba de propiedad en gráficos de grado acotado - Goldreich, Ron )Ω ( n ) Ω ( n--√)
fuente