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?
źródło
Odpowiedzi:
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.
źródło
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 :
źródło
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:
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.
źródło
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ę.
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.
Zależy od tego, co rozumiesz przez „kanoniczny”. AFAIK, nie ma zgody co do odpowiedzi na pytanie „kiedy w istocie dwa dowody są identyczne?”.
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:
źródło