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 podzbiór.
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 podzbiór.
Odpowiedzi:
Nie.
Nierozstrzygalne języki rozpoznawane przez Turinga mogą być jednoargumentowe (zdefiniuj chyba że , więc jedyne trudne łańcuchy składają się wyłącznie z zer). Twierdzenie Mahaneya mówi, że żaden język jednoargumentowy nie może być NP-kompletny, chyba że P = NP.