Czy każdy rozpoznawalny przez Turinga niezdecydowany język ma podzbiór NP? Pytanie to może być postrzegane jako silniejsza wersja faktu, że każdy nieskończony rozpoznawalny język Turinga ma nieskończony decydujący
To pytanie powstało w kontekście kryptografii, ale poniżej przedstawię je w kategoriach teorii złożoności, ponieważ ludzie tutaj są bardziej zaznajomieni z tym ostatnim. To pytanie dotyczy problemów w NP, ale nie w średniej P / poli i pokonania premii przez Oracle Access . Nieformalne...
Załóżmy, że P! = NP. Wiemy, że w każdej chwili możemy wykonać proste instancje 3-SAT. Możemy również wygenerować coś, co uważamy za trudne wystąpienie (ponieważ nasze algorytmy nie potrafią ich szybko rozwiązać). Czy jest coś, co przeszkadza, by zbiór twardych instancji był arbitralnie mały, o ile...