Konsekwencje

Wielu wierzy, że . Jednak wiemy tylko, że B P P znajduje się na drugim poziomie hierarchii wielomianowej, tj. B P P ⊆ Σ P 2 ∩ Π P 2 . Etap kierunku pokazano B P P = P jest najpierw doprowadzić go do pierwszego poziomu hierarchii, to znaczy wielomian B P P ⊆ N P .$\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$$\mathsf{BPP}$$\mathsf{BPP}\subseteq \Sigma^ \mathsf{P}_2 \cap \Pi^ \mathsf{P}_2$$\mathsf{BPP} = \mathsf{P}$$\mathsf{BPP} \subseteq \mathsf{NP}$

Ograniczenie oznaczałoby, że niedeterminizm jest co najmniej tak samo silny jak przypadkowość w czasie wielomianowym.

Oznacza to również, że jeśli w przypadku problemu możemy znaleźć odpowiedzi przy użyciu wydajnych algorytmów losowych (czas wielomianowy), wówczas możemy skutecznie zweryfikować odpowiedzi (w czasie wielomianowym).

Czy są jakieś znane interesujące konsekwencje dla ?$\mathsf{BPP} \subseteq \mathsf{NP}$

Czy istnieją powody, by sądzić, że udowodnienie jest obecnie poza zasięgiem (np. Bariery lub inne argumenty)?$\mathsf{BPP} \subseteq \mathsf{NP}$

Po pierwsze, udowodnienie z łatwością oznaczałoby, że N E X P ≠ B P P , co już oznacza, że ​​twój dowód nie może się relatywizować.$BPP \subseteq NP$$NEXP \neq BPP$

$coRP \subseteq NTIME[2^{n^{o(1)}}]$$NEXP \not\subset P/poly$

Osobiście nie wiem, dlaczego wygląda to „poza zasięgiem”, ale wydaje się, że trudno to udowodnić. Z pewnością potrzebne będą naprawdę nowe sztuczki, aby to udowodnić.