Em testes propriedade gráfico, um algoritmo de consulta um gráfico de alvo para a presença ou ausência de arestas e necessidades para determinar se o alvo quer tem uma certa propriedade ou é -muito de ter a propriedade. (Um algoritmo pode ser solicitado a ter sucesso com um erro lados ou dois lados.) Um gráfico é ε -muito de ter uma propriedade não se arestas pode ser adicionado / subtraído para torná-lo tem a propriedade.
Diz-se que uma propriedade é testável se puder ser testada da maneira especificada acima em um número sub-linear de consultas, ou melhor ainda, em um número de consultas independente de (mas não ). A noção de quais são as propriedades também pode ser formalizada, mas deve ficar clara.
Existem muitos resultados que caracterizam quais propriedades são testáveis, com muitos exemplos de propriedades testáveis naturais. No entanto, não conheço muitas propriedades naturais conhecidas por não serem testáveis (digamos, em um número constante de consultas) - uma com a qual estou familiarizado é testar o isomorfismo em um determinado gráfico.
Portanto, minha pergunta é: quais propriedades gráficas naturais são conhecidas por não serem testáveis?
Respostas:
No modelo de matriz de adjacência, há um limite inferior de na complexidade da consulta de testar se um gráfico de vértice consiste em duas cópias isomórficas de algum gráfico de -vertex (consulte Introdução às propriedades do gráfico de teste - Goldreich para uma pesquisa).n n / 2Ω(n) n n/2
Além disso, existem muitos limites inferiores que dependem de para testadores com erro unilateral, por exemplo: testing -Clique, -Cut e -Bisection (consulte Teste de propriedade e sua conexão com aprendizado e aproximação - Goldreich (Goldwasser, Ron )ρ ρ ρn ρ ρ ρ
Além disso, no modelo de gráfico de graus delimitados, o teste de 3-Colorability requer consultas , enquanto o teste de 2-Colorability (isto é, bipartida) requer (consulte Teste de propriedades em gráficos de graus limitados - Goldreich, Ron ).Ω ( √Ω(n) Ω(n−−√)
fonte