Czy wszystkie klasy złożoności mają charakterystykę języka liścia?

Języki liścia są pięknym sposobem na jednolite zdefiniowanie wielu klas złożoności. Większość klas złożoności jest zwykle określana przez model obliczeniowy (np. Deterministyczna / losowa TM) i związany z zasobami (czas dziennika, przestrzeń wielopunktowa itp.). Jednak w sformułowaniu języka liścia istnieje tylko jeden model obliczeń, a klasa jest określona przez podanie języka liścia.

Szczegóły są zbyt długie, aby je wyjaśnić, więc skieruję zainteresowanych czytelników do jednej z tych dwóch ankiet:

1. Jednolite charakterystyki klas złożoności według H. Vollmera
2. Lekcje języka liścia autorstwa KW Wagnera

Obie ankiety świetnie wyjaśniają formułę na pierwszych kilku stronach.

W ankiecie Wagnera powiedział: „okazuje się, że praktycznie każdą rozważaną do tej pory klasę złożoności można opisać językami liści”.

Moje pytanie dotyczy tego stwierdzenia. Wiem, że istnieją klasy, dla których nie znamy charakterystyki języka liścia, więc oznacza to, że albo klasy niekoniecznie mają taką charakterystykę, albo jej nie znaleźliśmy.

Czy oczekujemy, że każda klasa złożoności (powiedzmy między P i PSPACE) będzie miała charakterystykę języka liścia? (Ograniczmy się do „naturalnych” klas złożoności.) Czy w literaturze jest tego rodzaju wynik?

(Powiązane pytanie, na które z przyjemnością znałbym odpowiedź: czy istnieje (heurystyczna) metoda wymyślenia języka liścia dla danej klasy?)

EDYCJA: Suresh wskazuje, że w artykule w Wikipedii jest krótka definicja języków liści. Kopiuję to poniżej.

Kilka klas złożoności jest zazwyczaj definiowanych w kategoriach niedeterministycznej maszyny Turinga w czasie wielomianowym, w której każda gałąź może albo zaakceptować lub odrzucić, a cała maszyna akceptuje lub odrzuca jako pewną funkcję warunków gałęzi. Na przykład niedeterministyczna maszyna Turinga akceptuje, jeśli przynajmniej jedna gałąź akceptuje, i odrzuca tylko wtedy, gdy wszystkie gałęzie odrzucają. Z drugiej strony niedeterministyczna maszyna Turinga akceptuje tylko wtedy, gdy wszystkie gałęzie akceptują, i odrzuca, jeśli jakakolwiek gałąź odrzuca. W ten sposób można zdefiniować wiele klas.

Spójrz na

Bernd Borchert, Riccardo Silvestri: Charakterystyka klas języka liścia. Inf. Proces. Łotysz. 63 (3): 153-158 (1997) ( link doi tutaj )

Autorzy scharakteryzowali klasy języka liścia jako klasy, które są (a) „policzalne”, (b) są „zmniejszające się” ograniczane do wielu razy redukcję, oraz (c) „łączone do zamkniętych” (tj. Rozłączne związki) redukcja wielokrotna jeden.

Bardziej formalnie, że wszystkie języki w klasie językowej liść mają bijection z liczb naturalnych, a właściwość, że dla każdego , jeśli wtedy oraz ( oznacza rozłączny związek). Ponadto każda „klasa języka innego niż liść” zawiera język, który nie ma jednej z tych właściwości.$L$$C,D \in L$$E \leq^P_m C \sqcup D$$E \in L$$\sqcup$

Z tych trzech warunków możemy uzyskać wiele przykładów klas, które nie są lekcjami języka liściastego. Na przykład warunek „policzalny” wyklucza klasy porad, takie jak , a „zmniejszająca się wielokrotność redukowana wrt polytime wielokrotność jeden” wyklucza stałe klasy związane z zasobami, takie jak . (Przypomnij, że zwykły dowód, że wykorzystuje fakt, że nie jest zamknięta w ramach takich redukcji).$P/poly$$SPACE[n]$$SPACE[n] \neq P$$SPACE[n]$