Czy diagonalizacja oddaje istotę separacji klasowej?

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?

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.

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.$O$$O \subseteq \{0, 1\}^*$

$P$$NP$$P\ne NP$

$P^{PH} \subseteq IP$

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.

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$$PSpace$
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.)