Naturalne, niestabilne właściwości wykresu

Podczas testowania właściwości wykresu algorytm wysyła zapytanie do wykresu docelowego o obecność lub brak krawędzi i musi ustalić, czy cel ma określoną właściwość, czy też jest -far od posiadania tej właściwości. (Algorytm może zostać poproszony o powodzenie z błędem 1-stronnym lub 2-stronnym.) Wykres ma -far od posiadania właściwości, jeśli nie można dodać / odjąć krawędzi aby utworzyć ma właściwość. $\epsilon$ $\epsilon$ $\epsilon \binom{n}{2}$

Mówi się, że właściwość jest testowalna, jeśli można ją przetestować w sposób określony powyżej w subliniowej liczbie zapytań lub jeszcze lepiej w szeregu zapytań niezależnych od $n$ (ale nie $\epsilon$ ). Pojęcie tego, jakie są właściwości, można również sformalizować, ale powinno być jasne.

Istnieje wiele wyników charakteryzujących właściwości, które można testować, z wieloma przykładami naturalnych właściwości testowalnych. Nie jestem jednak świadomy wielu naturalnych właściwości, o których wiadomo, że nie są testowalne (powiedzmy w stałej liczbie zapytań) - jednym z nich jest testowanie izomorfizmu na danym wykresie.

Moje pytanie brzmi zatem: jakie naturalne właściwości grafu nie są testowalne?

— Lew Reyzin
źródło

(1) Aby wyjaśnić, czy szukasz takich właściwości w sąsiednim modelu macierzowym? W modelu listy sąsiedztwa (który różni się od napisanego przez ciebie sformułowania) wiele problemów wymaga więcej niż stałej liczby zapytań. (2) Prawdopodobnie wiesz o tym, ale Goldreich, Goldwasser i Ron (propozycja 10.2.3.2 JACM 1998 ) dowodzą, że w NP istnieje (niekoniecznie naturalna) właściwość graficzna, która wymaga kwerend Ω (n ^ 2) przy użyciu metoda probabilistyczna.

— Tsuyoshi Ito,

Dzięki - model macierzy przylegania jest w porządku. Znam ich wynik, ale chciałbym wyrazić naturalne właściwości, a nie istnienie niektórych właściwości.

— Lew Reyzin

Nie jestem tego pewien, więc nie wymienię tego jako odpowiedzi, ale myślę, że pojemność Shannona wykresu

Θ (G)

$\Theta(G)$ nie jest testowalna. mathworld.wolfram.com/ShannonCapacity.html

— Dimitris,

W modelu macierzy przylegania istnieje dolna granica w złożoności zapytania sprawdzania, czy wykres wierzchołków składa się z dwóch izomorficznych kopii niektórych wykresów odwróconych (patrz Wprowadzenie do testowania właściwości wykresu - Goldreich do ankiety). $\Omega(n)$ $n$ $n/2$

Ponadto istnieje wiele dolnych granic, które zależą od dla testerów z jednostronnym błędem, np .: testowanie -Clique, -Cut i -Bisection (patrz Testowanie właściwości i jego związek z uczeniem się i przybliżaniem - Goldreich , Goldwasser, Ron ) $n$ $\rho$ $\rho$ $\rho$

Ponadto w modelu grafu z ograniczonym stopniem testowanie 3-kolorowalności wymaga zapytań , podczas gdy testowanie 2-kolorowalności (tj. Dwustronność) wymaga (patrz Testowanie właściwości w grafach stopni ograniczonych - Goldreich, Ron ). $\Omega(n)$ $\Omega(\sqrt n)$