Jakie są naturalne przykłady dowodów nierelatywnych?

Jak rozumiem, dowód, że P = NP lub P ≠ NP musiałby być nierelatywny (jak w wyroczniach teorii rekurencji).

Praktycznie wszystkie dowody wydają się być relatywne.

Jakie są dobre przykłady spoza relativizable dowodów, w tym rodzaju, że P = NP / P ≠ NP dowód musiałby być, że nie są błahe albo wymyślone?

(Nie jestem teoretykiem rekurencji, więc proszę wybaczyć brak cytatów).

[EDYCJA: lepszy post matematyczny ]

$\mathsf{IP} = \mathsf{PSPACE}$$A$$\mathsf{IP}^A \ne \mathsf{PSPACE}^A$$\mathsf{PSPACE}$-kompletny problem TQBF podaje się, rozważając rozszerzenie skwantyfikowanego wzoru logicznego na wielomian niskiego stopnia na odpowiednio dużym polu. Jeśli otrzymamy relatywizowaną formułę logiczną (z bramkami wyroczni), takie rozszerzenie nie istnieje.

$\mathsf{C} \subseteq \mathsf{D}$$A$$\tilde{A}$$A$$\mathsf{C}^A \subseteq \mathsf{D}^{\tilde{A}}$$\mathsf{C} \not \subset \mathsf{D}$$A$$\tilde{A}$$\mathsf{C}^{\tilde{A}} \not \subset \mathsf{D}^{A}$. Aaronson i Wigderson pokazują, że algebryzy, ale wiele innych wyników, w tym , nie.$\mathsf{IP} = \mathsf{PSPACE}$$\mathsf{NP} \not \subset \mathsf{P}$

Najnowszym przykładem techniki, która nie łączy się i nie relatywizuje, jest dowód Ryana Williamsa, że . Oddzielenie nie algebrize: jest wyrocznią i niskiego stopnia rozszerzenia tak, że . Intuicyjnie powodem, dla którego dowód unika bariery, jest to, że polega ona na istnieniu szybszego niż trywialny algorytmu satysfakcji dla$\mathsf{NEXP} \not \subset \mathsf{ACC}$$A$$\tilde{A}$$\mathsf{NEXP}^{\tilde{A}} \subset \mathsf{ACC}^A$$\mathsf{ACC}$obwody, a algorytm wykorzystuje nierelatywizujące i niealgebryzujące właściwości takich obwodów. Ryan zauważa w artykule, że wszystkie znane szybsze niż trywialne algorytmy satysfakcji psują się po dodaniu wyroczni lub algebraicznych rozszerzeń wyroczni.

Istnieje również interesujące podejście do rozumienia relatywizacji za pomocą logiki. W starym manuskrypcie Arora, Impagliazzo i Vazirani definiują system aksjomatów w taki sposób, że wyniki relatywizacji są dokładnie tymi, które wynikają z aksjomatów, a wyniki nie relatywizujące są niezależne od systemu. Artykuł Impagliazzo, Kabanets i Kolokolova robi coś podobnego dla algebrizacji, wprowadzając dodatkowy aksjomat do tych zdefiniowanych przez Arorę, Impagliazzo i Vazirani. Pokazują, że najbardziej znane wyniki nierelatywizujące wynikają z ich aksjomatów, podczas gdy P vs NP, między innymi, jest od nich niezależny.

Przepraszam, jeśli coś źle zrozumiałem, nie jestem ekspertem.

Oto lista niepowiązanych dowodów:

1. Twierdzenie PCP

2. Zobowiązanie zależne od instancji oznacza protokół zerowej wiedzy:
   równoważność zerowej wiedzy i zobowiązań

3. Nie ma wydajnego zaciemniacza obwodu „wirtualnej czarnej skrzynki” dla obwodów ogólnych:
   Równoważność między zerową wiedzą a zobowiązaniami

4. PSPACE można sprowadzić do oceny zwięzłego produktu : PSPACe przetrwa trzy-bitowe wąskie gardła$S_5$
   

5. Przeciw nieplątanym dowodom, NEXP ma minimalnie interaktywne systemy dowodzenia z 2 dowodami: Systemy dowodzenia z
   dwoma dowodami: ich moc i problemy

6. Przeciw potencjalnie uwikłanym dowodom, NEXP ma bardziej interaktywne protokoły MIP:
   interaktywny dowód dla wielu dźwięków NEXP przeciwko splątanym dowodom

7. NP ma sprawdzone dowody wiedzy NISZK z doskonałym wydobywaniem wiedzy w modelu „ukrytych bitów„ efektywnie próbkowalnej dystrybucji niestandardowej ”, oraz dowody wiedzy NIPZK o wydajnej wiedzy w (prawdziwych) ukrytych bitach. Ponadto, jeśli próbnik może mieć małe prawdopodobieństwo wyprowadzenia (a dźwięk jest wymagany tylko wtedy, gdy sampler nie wysyła ), wówczas „NISZK” z poprzedniego zdania można zastąpić „NIPZK” . Jonathan Katz, Zaawansowane tematy w kryptografii, Wykład 13$\perp$$\perp$
   
   Uwaga: Doskonałe wyodrębnianie wiedzy następuje po sprawdzeniu poprawności części na stronie 2. (Nie-doskonałe) wyodrębnianie wiedzy zachowuje się z tego samego powodu, co nie-doskonała solidność, jak opisano na górze strony 5. Doskonała zerowa wiedza może można uzyskać poprzez użycie przez symulator macierzy Hamiltonian jako jego permutacji oraz niektórych rzeczywistych ciągów bitów odpowiadających bitom tendencyjnym o wartości 0 jako takiej, głównie w różnych lokalizacjach. Następnie następuje zdanie „posiadające wyjście próbnika$C_i$$\pi$$\perp$ gdyby nie był w stanie wybrać elementu z {0,1,2,3, ..., n! -1} idealnie równomiernie w wystarczająco krótkim czasie, ponieważ taki wybór pozwoliłby na idealnie jednolite wygenerowanie macierz grafu z ukierunkowanym cyklem lub permutacja wierzchołków.

jest to miła ankieta w tej dziedzinie przeprowadzona przez wiodącego eksperta, która podsumowuje / wyszczególnia niektóre punkty innych dotychczasowych odpowiedzi i zawiera dodatkowe przykłady.

[1] Rola relatywizacja złożoności obliczeniowej Fortnow

Kilka ostatnich nierelatywizujących wyników w dziedzinie dowodów interaktywnych skłoniło wiele osób do oceny znaczenia relatywizacji. W tym artykule przyjrzymy się, w jaki sposób teoretycy złożoności wykorzystują i niewłaściwie wykorzystują wyniki wyroczni. Zwracamy szczególną uwagę na nowe interaktywne systemy sprawdzające i wyniki sprawdzania programów i staramy się zrozumieć, dlaczego nie są one relatywizowane. Dajemy nowe wyniki, które mogą pomóc nam lepiej zrozumieć te pytania.