Tytuł mniej więcej mówi wszystko, ale myślę, że mógłbym dodać trochę tła i kilka konkretnych przykładów, którymi jestem zainteresowany.
Teoretycy złożoności opisowej, tacy jak Immerman i Fagin, scharakteryzowali wiele najbardziej znanych klas złożoności za pomocą logiki. Na przykład NP można scharakteryzować za pomocą zapytań egzystencjalnych drugiego rzędu; P można scharakteryzować za pomocą zapytań pierwszego rzędu z dodanym operatorem najmniej ustalonego punktu.
Moje pytanie brzmi: czy były jakieś próby, szczególnie udane, wymyślenia takich reprezentacji dla klas złożoności kwantowej, takich jak BQP lub NQP? Jeśli nie, dlaczego nie?
Dziękuję Ci.
Aktualizacja (moderator) : odpowiedź na to pytanie jest całkowicie udzielona na mathoverflow .
Odpowiedzi:
Myślę, że odpowiedź jest Robins do mojego pytania o MO odpowiada również ten.
Opisowe złożoność charakterystyka klasa złożoności daje język, którego zapytań (tj wzorów) są dokładnie takie funkcje obliczalne w . Składnia języka jest zwykle bardzo prosta, tzn. Biorąc pod uwagę ciąg łatwo jest sprawdzić, czy jest poprawnie sformułowanym zapytaniem języka, przynajmniej oczekuje się, że będzie rozstrzygalne (ale zwykle sprawdzenie składni można wykonać w mała klasa złożoności). Wiązałoby się to skuteczne enumerablity problemów w klasie i dałoby składniowej charakteryzację dla . (Jeśli złożoność sprawdzania składni jest niska, może to również sugerować istnienie pełnego problemu dla klasy.)C q q C CC C q q C C
W powyższych komentarzach Robin powiązał artykuł Korda Eickmeyera i Martina Grohe'a „ Randomizacja i derandomizacja w teorii złożoności opisowej ”, który daje charakterystykę pod względem „złożoności opisowej” . Sami autorzy zauważają we wstępie, że różni się to od tego, co zwykle oznacza opisowa charakterystyka złożoności:BPP
Nie jestem ekspertem od teorii modeli skończonych / złożoności opisowej (i osobiście chciałbym usłyszeć więcej od ekspertów), ale mam wrażenie, że jest tu trochę oszustwa, mówiąc, że jest to opisowa charakterystyka złożoności. Powodem mojego odczucia jest to, że jeśli pozwolimy sobie na nieefektywną składnię, możemy zastosować dowolne ograniczenia semantyczne, aby ograniczyć klasę dobrze sformułowanych zapytań i możemy nadać charakterystykę „złożoności opisowej” dowolnej klasie złożoności. Weźmy na przykład (który przechwytuje ), a następnie weź dokładnie te zapytania, które są obliczalne w ; lub rozważ język, który ma jeden symbol funkcji dla każdej maszyny w . Oba z nich przechwytująP S p a c e B Q P B Q P B Q PSO(TC) PSpace BQP BQP BQP ale nie mają skutecznej składni.
źródło
źródło