Testowanie właściwości w innych metrykach?

Istnieje duża literatura na temat „testowania właściwości” - problemu polegającego na utworzeniu niewielkiej liczby zapytań do czarnej skrzynki do funkcji celu rozróżnienia dwóch przypadków:$f\colon\{0,1\}^n \to R$

1. $f$ jest członkiem pewnej klasy funkcji$\mathcal{C}$

2. $f$ jest -far z każdej funkcji w klasie .$\varepsilon$$\mathcal{C}$

Zakres funkcji jest czasem wartością logiczną: , ale nie zawsze.$R$$R = \{0,1\}$

Tutaj, -far jest ogólnie rozumiany jako odległość Hamminga: ułamek punktów który musiałby zostać zmieniony, aby umieścić w klasie . Jest to naturalna metryka, jeśli ma zakres boolowski, ale wydaje się mniej naturalna, jeśli powiedziano, że zakres ma wartość rzeczywistą.$\varepsilon$$f$$f$$\mathcal{C}$$f$

Moje pytanie: czy istnieje nić literatury na temat testowania właściwości, która testuje bliskość niektórych klas w odniesieniu do innych metryk?$\mathcal{C}$

Tak jest! Podam trzy przykłady:

1. Biorąc pod uwagę zbiór S i „tablicę mnożenia” przez S x S, rozważ problem ustalenia, czy dane wejściowe opisują grupę abelową, czy też jest daleka od niej. Friedl, Ivanyos i Santha w STOC '05 pokazał, że nie jest testerem nieruchomość z kwerendy złożoności polylog (| S |), gdy odległość jest miarą stosunku do odległości edycji mnożenia tabel, które umożliwia dodawanie i usuwanie wierszy i kolumn z tabliczka mnożenia. Ten sam problem został również rozważony w modelu odległości Hamminga przez Erguna, Kannana, Kumara, Rubinfelda i Viswanathana (JCSS '00), gdzie wykazali złożoność zapytań O ~ (| S | ^ {3/2}).

2. Dużo pracy wykonano na testowaniu właściwości wykresów, gdzie wykresy są reprezentowane za pomocą list przyległości, a stopień każdego wierzchołka jest ograniczony. W tym przypadku model odległości nie jest dokładnie odległością Hamminga, ale raczej liczbą krawędzi, które można dodać lub usunąć, zachowując stopień ograniczenia.

3. W ściśle powiązanym badaniu testowania właściwości rozkładów badano różne pojęcia odległości między rozkładami. W tym modelu dane wejściowe są rozkładem prawdopodobieństwa dla pewnego zestawu, a algorytm uzyskuje do niego dostęp poprzez próbkowanie ze zbioru zgodnie z nieznanym rozkładem. Algorytm jest następnie wymagany do ustalenia, czy rozkład spełnia jakąś właściwość, czy też jest „daleki” od niej. Badano tutaj różne pojęcia odległości, takie jak L_1, L_2, robot ziemny. Badano także rozkłady prawdopodobieństwa w nieskończonych domenach ( Adamaszek-Czumaj-Sohler, SODA '10 ).

Zwykle nie jest to nazywane testowaniem właściwości (a tak naprawdę nie jest), ale istnieje duży wysiłek w podejmowaniu decyzji o właściwościach macierzy poprzez spojrzenie na małą, indukowaną nieletnią. Jest to bardzo podobne do celu w testowaniu nieruchomości. Zobacz na przykład artykuł Rudelsona i Vershynina:

http://portal.acm.org/citation.cfm?id=1255449

Istnieją wcześniejsze artykuły Frieze-Kannana. Chodzi o to, że zazwyczaj stosowaną miarą jest pewna norma matrycowa, taka jak norma widmowa, norma Frobeniusa lub norma cięcia. Jeśli chcesz, możesz pomyśleć o niektórych z tych wyników jako algorytmach testowania właściwości w metrykach innych niż odległość Hamminga.

$f\colon [n]^d\to \mathbb{R}$$L_p$$p\geq 1$$L_p$

$L_p$

$L_1$$L_1$$L_1$$n$$1$

$L_p$

$k$