Czy diagonalizacja oddaje istotę separacji klasowej?

11

Nie pamiętam, że widziałem separację klas nieopartą na wynikach diagonalizacji i relatywizacji. Diagonalizacja może być nadal używana do oddzielania pozostałych znanych klas, ponieważ argumenty nierelatywizujące mogą być nadal stosowane w konkluzji o diagonalizacji lub w konstrukcji diagonalizowanej maszyny Turinga. Oto kilka powiązanych pytań:

Czy istnieją dowody separacji klas nieoparte na przekątnej?

A jeśli tak

Czy możemy znaleźć za nimi mechanizm samoreferencji?

Dalej,

czy każda separacja klas ma „kanoniczny naturalny” dowód (w sensie nieformalnym)?

Jeśli tak, powinniśmy spróbować znaleźć argumenty nie relatywizujące zamiast innych schematów dowodowych dla otwartych pytań.

Czy każdy dowód nieprzeznaczony na przekątnej można przepisać na dowód po przekątnej?

Ludovic Patey
źródło
Zredagowałem pytanie, aby ułatwić czytanie. Przepraszam, jeśli zmieniłem twój zamiar.
András Salamon
@ András Dziękujemy za wydanie. Często jestem niejasny. Jest jedna zmiana: miałem na myśli, że diagonalizacja nie zawiodła, ponieważ w niej możemy użyć argumentów nierelatywizujących. Myślę, że relatywizacja i diagonalizacja są ortogonalne. I nie uważam, że dowody, które nie wykorzystują diagonalizacji, wykorzystywałyby mechanizm głębokiego autoreferencji, ale tylko to, że w głębokim zrozumieniu dowodu moglibyśmy odkryć głęboki mechanizm autoreferencji ^^. Zmienię te szczególne punkty.
Ludovic Patey

Odpowiedzi:

15

Zależy od tego, jak sformalizujesz diagonalizację. Kozen ma artykuł, który pokazuje, że separacja klas złożoności musi być dowodem przekątnej.

Lance Fortnow
źródło
+1 Myślę, że przeczytałem to na twoim blogu i czekałem na twoją odpowiedź :)
Mohammad Al-Turkistany
5

Ponieważ relatywizacja diagonalizacji jest relatywistyczna, żaden wynik złożoności implikujący sprzeczne relatywizacje nie może być oparty na diagonalizacji. Cytując Arora-Barak :

Wyniki udowodnione wyłącznie przy użyciu diagonalizacji relatywizują się w tym sensie, że dotyczą one TM z wyrocznią z dostępem do , dla każdej wyroczni O { 0 , 1 } . Możemy to wykorzystać, aby pokazać ograniczenia takich metod. W szczególności same metody relatywizacji nie mogą rozwiązać pytania P vs. NP.OO{0,1}

P.N.P.P.N.P.

P.P.H.jaP.

MS Dousti
źródło
2
Zauważ, że Baker, Gill i Solovay nie stwierdzili, że diagonalizacja nie może działać, ale wypowiedzieli się w bardziej szczegółowy sposób: „Wydaje się mało prawdopodobne, aby zwykłe metody diagonalizacji były odpowiednie”.
András Salamon
@Sadeq Nie zgadzam się, że przekątna relatywizuje się. Na przykład można zdefiniować maszynę ukośną na podstawie właściwości, biorąc pod uwagę właściwość położenia obliczeniowego, która nie jest relatywizowana.
Ludovic Patey
Algebriacja nie jest techniką, ale raczej koncepcją podobną do relatywizacji. Podejrzewam, że masz na myśli arytmetyzację. A jaki jest związek z naturalnymi dowodami?
Kristoffer Arnsfelt Hansen
1
@Sadeq: BGS wyraźnie pozwoliły na szerszą definicję diagonalizacji, niż wydaje się zamierzać Arora-Barak. Jeśli ustalony teoretyk, jak Robert Solovay, uważa, że ​​mogą istnieć inne pojęcia diagonalizacji, które nie relatywizują, to być może powinniśmy pozostawić tę możliwość otwartą. Uwaga na stronie 75 A&B nie odrzuca możliwości, że pewien rodzaj diagonalizacji wykorzystuje nierelatywizujący fakt dotyczący maszyn Turinga; wciąż nieopublikowany rękopis Arora-Impagliazzo-Vazirani wskazuje na dość subtelne kwestie. cseweb.ucsd.edu/~russell/ias.ps
András Salamon
1
Trwa na ten temat debata: patrz na przykład odpowiedź Fortnow na artykuł AIV: people.cs.uchicago.edu/~fortnow/papers/relative.pdf
Suresh Venkat
5

Aby dodać do odpowiedzi Fortnow, kontynuując pracę Kozen, Nash, Impagliazzo i Remmel sformalizowali pojęcie silnej diagonalizacji i podali pewne dowody, że nie relatywizuje się. Aby częściowo odpowiedzieć na twoje pierwsze pytanie, ich wyniki pokazują, że niektóre dowody separacji klas nie mogą opierać się na silnej przekątnej. Oto streszczenie:

Definiujemy i badamy silną diagonalizację i porównujemy ją ze słabą diagonalizacją, ukrytą w [7]. Wynik Kozen w [7] pokazuje, że praktycznie każdy rozdział można przekształcić jako słabą diagonalizację. Pokazujemy, że istnieją klasy języków, których nie da się rozdzielić silną diagonalizacją i dostarczamy dowodów, że silna diagonalizacja nie relatywizuje się. Definiujemy również dwa rodzaje pośredniej diagonalizacji i badamy ich moc.

Ponieważ definiujemy silną diagonalizację w kategoriach języków uniwersalnych, badamy ich złożoność. Rozróżniamy i porównujemy słabe i surowe uniwersalne języki. Na koniec analizujemy niektóre pozornie słabsze warianty języków uniwersalnych, które nazywamy językami pseudouniwersalnymi, i pokazujemy, że w warunkach słabego zamknięcia łatwo dają uniwersalne języki.

1-Nash, A., Impagliazzo, R., Remmel; J. „Universal Languages ​​and the Power of Diagonalization”. 18. doroczna konferencja IEEE na temat złożoności obliczeniowej (CCC'03), s. 1. 337, 2003.

Mohammad Al-Turkistany
źródło
5

Czy istnieją dowody separacji klas nieoparte na przekątnej?

Tak, istnieją, ale nie dla jednolitych klas złożoności. Nie mamy argumentów, aby wykluczyć takie dowody, ale do tej pory wszelkie separacje między klasami jednolitej złożoności wydają się w pewnym miejscu wykorzystywać diagonalizację.

Czy możemy znaleźć za nimi mechanizm samoreferencji?

Nie sądzę, że niejednolite separacje klas złożoności można przekształcić w argumenty „samoodniesienia”, ponieważ nie są one klasami jednolitymi i nie można ich wyliczyć, a dla argumentu samoodniesienia musimy wyliczyć członków klasy.

czy każda separacja klas ma „kanoniczny naturalny” dowód (w sensie nieformalnym)?

Zależy od tego, co rozumiesz przez „kanoniczny”. AFAIK, nie ma zgody co do odpowiedzi na pytanie „kiedy w istocie dwa dowody są identyczne?”.

Jeśli tak, powinniśmy spróbować znaleźć argumenty nie relatywizujące zamiast innych schematów dowodowych dla otwartych pytań. Czy każdy dowód nieprzeznaczony na przekątnej można przepisać na dowód po przekątnej?

Jak zauważyli inni, odpowiedź zależy od tego, co rozumiesz przez diagonalizację. W bardziej ogólnym znaczeniu (artykuł Kozen'a połączony przez Lance'a) odpowiedź brzmi „tak” dla dowolnych dwóch różnych „klas złożoności” (jak zdefiniowano w artykule Kozen'a). Możesz zamienić argument na argument „diagonalizacji”. Ale:

  1. nie dotyczy to klas złożoności, które nie spełniają wymagań określonych w pracy Kozen'a (tj. nie są to „klasy złożoności” Kozen).
  2. P.P.S.pzadomi
  3. ważne jest to, że im bardziej ogólna jest metoda, tym bardziej ograniczone są jej zastosowania (jeśli jest używana samodzielnie), ponieważ metoda musi działać w większej liczbie przypadków, a to jest ograniczenie metody, nie możemy użyć konkretnego informacje, które posiadamy na temat problemu, jeśli nie są udostępniane lub nie można ich zastąpić czymś podobnym w przypadku innych problemów, które chcemy zastosować do tej metody.
  4. Możemy przekształcić argumenty separacji w argumenty „diagonalizacji” (biorąc pod uwagę ograniczenie, o którym wspomniałem powyżej), ale sam fakt, że „funkcja diagonalizacji naprawdę dzieli klasy”, wymaga dowodu. Artykuł Kozen'a pokazuje, że istnieje funkcja przekątna, jeśli klasy są różne, ale skąd możemy wiedzieć, że dana funkcja jest naprawdę przekątna? Potrzebujemy dowodu! A artykuł (AFAIU) nie daje nam żadnego pomysłu, jak wymyślić te dowody. Jeśli mamy argument separacyjny, możemy go przekształcić w dowód przekątnej, ale to dopiero potemmieć dowód. Oryginalny dowód posłuży jako część nowego dowodu przekątnej, pokaże, że funkcja jest naprawdę przekątna. (W pewnym sensie dowód przekątnej skonstruowany z pracy Kozen nie będzie „kanoniczny”, ponieważ będzie całkowicie zależny od pierwotnego argumentu.)
Kaveh
źródło
Powinienem bardziej uważać na twoje drugie pytanie (czy możemy znaleźć za nimi mechanizm samoreferencji?) I niejednorodność. Myślę, że musisz sprecyzować, co rozumiesz przez „mechanizm samookreślenia”. Słowo „samo-odniesienie” jest jednym ze słów, które są często niewłaściwie używane (szczególnie w dziełach filozoficznych), dlatego powinniśmy być ostrożni. Zwykły mechanizm autoreferencji (w sensie Godela, patrz także książka R. Smullyana „Diagonalizacja i autoreferencja”, 1994) wymaga wyliczenia obiektów (tutaj TM) mniejszej klasy w języku. Ale są też inni, którzy również korzystają
Kaveh
użyj słowa „samookreślenie”. EgK Mulmuley używa go w nierównomiernym otoczeniu swojego GCT w czymś, co nazywa „paradoksem odniesienia”. Trudno mi jednak stwierdzić, czy właśnie to masz na myśli, gdy używasz „mechanizmu samookreślenia”.
Kaveh