Czy są jakieś referencje na ten temat?
Czy są jakieś referencje na ten temat?
Odpowiedzi:
Oprócz sugerowania, że NP = co-NP, oznaczałoby to również, że BQP zawiera NP.
Wydaje się również sugerować, że trudne przypadki problemów z NP-zupełnością były łatwe do wygenerowania.
Ponieważ wiadomo, że rozkład na czynniki całkowite występuje zarówno w NP, jak i w ko-NP , dowód, że jest on w pełni NP , oznaczałby, że NP = co-NP , co uważa się za bardzo mało prawdopodobne.
Ciekawa dyskusja na temat tego starego postu autorstwa Lance'a Fortnowa .