Czy istnieje naturalny problem natury naturalnej, który jest NP-zupełny?

Dowolną liczbę naturalną można traktować jako sekwencję bitową, więc wprowadzenie liczby naturalnej jest takie samo, jak wprowadzenie sekwencji 0-1, więc oczywiście występują problemy NP-zupełne z wejściami naturalnymi. Ale czy są jakieś naturalne problemy, tzn. Takie, które nie używają kodowania i specjalnej interpretacji cyfr? Na przykład „Czy na pierwsze?” jest takim naturalnym problemem, ale ten jest w P. Lub „Kto wygrywa grę Nim ze stertami wielkości 3, 5, n, n?” to kolejny problem, który uważam za naturalny, ale wiemy również, że jest w P. Interesują mnie również inne klasy złożoności zamiast NP.

Aktualizacja: Jak zauważył Emil Jeřábek, biorąc uwagę aby ustalić, czy ma rozwiązanie w stosunku do naturali, jest NP-zupełne. Właśnie to miałem na myśli jako naturalne, tyle że tutaj dane wejściowe to trzy liczby zamiast tylko jednej.$a,b,c\in \mathbb N,$$ax^2+by-c=0$

Aktualizacja 2: Po ponad czterech latach oczekiwania Dan Brumleve podał „lepsze” rozwiązanie - pamiętaj, że wciąż nie jest ono ukończone z powodu losowej redukcji.

Ten problem ma wariację z jednym wejściem całkowitym:

Czy ma dzielnik ściśle pomiędzy dwoma największymi czynnikami pierwszymi?$n$

Chodzi o to, aby zastosować tę samą losową redukcję z sumy podzbioru opisanej w górnej odpowiedzi na powiązane pytanie, ale z zakresem docelowym zakodowanym jako dwie największe liczby pierwsze zamiast podawanych osobno. Definicja ma naturalny wygląd, mimo że jest to tylko funkcja parowania w przebraniu.

Oto kolejna odmiana tego samego problemu, z podobną redukcją problemu partycji:

Czy jest iloczynem dwóch liczb całkowitych, które różnią się o mniej niż ?$n$$n^{\frac{1}{4}}$

W obu redukcjach „kamuflujemy” zbiór liczb całkowitych, znajdując pobliskie liczby pierwsze i biorąc ich produkt. Jeśli można to zrobić w czasie wielomianowym, problemy te są NP-zupełne.

Myślę, że dobrze jest spojrzeć na te przykłady wraz z twierdzeniem Mahaneya : jeśli i możemy znaleźć pobliskie liczby pierwsze, to zbiory te nie są rzadkie. Satysfakcjonujące jest otrzymanie czysto arytmetycznego stwierdzenia z teorii złożoności (nawet jeśli jest to tylko przypuszczenie i można je łatwo udowodnić w inny sposób).$P \ne NP$

W oparciu o dyskusję opublikuję to jako odpowiedź.

Jak udowodnili Manders i Adleman , następujący problem jest NP-zupełny: biorąc pod uwagę liczby naturalne , określają, czy istnieje liczba naturalna taka, że .$a,b,c$$x\le c$$x^2\equiv a\pmod b$

Problem ten można równoważnie sformułować następująco: podany określić, czy kwadratowy jest rozwiązaniem .$b,c\in\mathbb N$$x^2+by-c=0$$x,y\in\mathbb N$

(Oryginalny artykuł podaje problem z , ale nietrudno dostrzec, że można go zredukować do przypadku ).$ax^2+by-c$$a=1$

Oto problem z pojedynczą liczbą naturalną jako wejściem.$\text{NEXP}$

Problem polega na kafelkowaniu siatki za pomocą stałego zestawu płytek i ograniczeń na sąsiadujących płytkach i płytkach na granicy. Wszystko to jest częścią specyfikacji problemu; nie jest częścią danych wejściowych. Dane wejściowe to tylko liczba . Problemem jest dla pewnego wyboru reguł kafelkowania, jak pokazano w$n \times n$$n$$\text{NEXP}$

D. Gottesman, S. Irani, „Kwantowa i klasyczna złożoność problematyki niezmiennie kafelków i problemów hamiltonowskich”, Proc. 50. roczna symp. on Foundations of Computer Science, 95-104 (2009), DOI: 10.1109 / FOCS.2009.22 . Również arXiv: 0905.2419 .

Problem zdefiniowano na stronie 5 wersji arxiv.

Dodatkowo definiują również podobny problem, którym jest -kompletny, który jest kwantowym analogiem kwantowym . (Klasycznym ograniczonym błędem analogowym z jest .)$\text{QMA}_\text{EXP}$$\text{NEXP}$$\text{NEXP}$$\text{MA}_\text{EXP}$

Myślę, że używając jednego z ograniczonych czasowo wariantów złożoności Kołmogorowa, możesz zbudować problem, który używa tylko binarnej reprezentacji liczby i (myślę, że) prawdopodobnie nie będzie w ; nieoficjalnie jest to rozstrzygająca wersja problemu „Czy ściśliwy?”:$\mathsf{P}$$n$

Problem: Biorąc pod uwagę , czy maszyna Turinga istnieje tak, że i na pustej taśmie w mniej niż krokach, gdzie jest długością reprezentacji binarnej$n$$M$$|M| < l$$M$$n$$l^2$$l = \lceil \log{n} \rceil$$n$

Wyraźnie jest w , ponieważ biorąc pod uwagę i , po prostu symuluj dla kroków i jeśli przestanie, porównaj wynik z .$\mathsf{NP}$$n$$M$$M$$l^2$$n$

Nasz artykuł FOCS'17 na temat krótkiej arytmetyki Presburgera jest przykładem „naturalnego” problemu, jakim jest NP-c, i wykorzystuje stałą liczbę liczb całkowitych na wejściu, powiedzmy . Różni się od Mandersa-Adlemana tym, że wszystkie ograniczenia są nierównościami. Zobacz post na blogu Gila Kalai, aby uzyskać dodatkowe informacje. $C$$C< 220$

Co z problemem PARTYCJI ?