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

30

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.

— domotorp
źródło

1

Wiem o problemie z kafelkami NEXP-complete, w którym wejściem jest liczba całkowita n, a problemem jest ustalenie, czy istnieje poprawne kafelkowanie siatki nxn. Jeśli to cię interesuje, poszukaj papieru.

— Robin Kothari,

2

@Emil: komentarz domotorp był odpowiedzią na zamieszanie. Ale to było nieporozumienie z mojej strony, więc usunąłem komentarz. Myślę, że wejście musi być pojedynczą liczbą naturalną, która nie powinna niczego kodować.

— Robin Kothari,

8

@domotorp: NP-zupełny problemem przeznaczona jest dana określić czy ma rozwiązanie . Innym wariantem jest, biorąc uwagę , określenie, czy istnieje taki, że

. (Wynik pochodzi z dx.doi.org/10.1145/800113.803627 .)

a, b, c \in N

$a,b,c\in\mathbb N$

a x^{2} + b y - c = 0

$ax^2+by-c=0$

x, y \in N

$x,y\in\mathbb N$

a, b, c

$a,b,c$

x \leq c

$x\le c$

x^{2} \equiv a (\mod b)

$x^2\equiv a\pmod b$

— Emil Jeřábek wspiera Monikę

3

Dlaczego odpowiedź na to pytanie nie jest oczywiście NIE ? Każdy trudny problem związany z NP ma instancje, które „kodują” obwód logiczny; prawdopodobnie właśnie to oznacza bycie twardym NP!

— Jeffε

2

@domotorp: być może innym dobrym „naturalnym” kandydatem jest problem ze znalezieniem minimalnych łańcuchów dodawania pojedynczej podanej liczby : z On On Number of Minimal Add Chain Chains : „... Problem ze znalezieniem minimalnego łańcucha addycyjnego dla zestawu o liczb jest NP-zupełny. nie oznacza to, co jest czasem stwierdził, że znalezienie minimalnej łańcuch dodatek dla jest NP-zupełny. Jednakże, można łatwo wywnioskować, że problem znalezienia wszystkie minimalne łańcuchy addycyjnych przez szereg jest NP-complete ... "

n

$n$

m

$m$

n

$n$

n

$n$

— Marzio De Biasi

17

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$

— Dan Brumleve
źródło

co rozumiesz przez „jeśli P ≠ NP, a my możemy znaleźć pobliskie liczby pierwsze”?

— T ....

1

@ao., patrz odpowiedź Petera Shora opisująca redukcję. Na jej NP-zupełny trzeba móc znaleźć doskonałą o w czasie . Postaram się tutaj opisać to wszystko później.

p

$p$

| p - n | < n^{a}

$\vert p - n \vert \lt n^a$

O ((\log n)^{k})

$O((\log{n})^k)$

— Dan Brumleve,

Które zestawy nie są gęste?

— T ....

33

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$

— Emil Jeřábek wspiera Monikę
źródło

10

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}$

— Robin Kothari
źródło

3

+1, ale trochę trudno argumentować, że liczba jest używana w „naturalny” sposób, ponieważ koduje dane wejściowe do konkretnej maszyny Turinga (konkretnie, kafelkowanie istnieje, jeśli maszyna Turinga akceptuje , gdzie jest w wyliczeniu potencjalnych ciągów wejściowych). Nadal bardzo interesujący wynik.

n

$n$

x

$x$

x

$x$

n

$n$

— mjqxxxx,

Maksymalnie zgadzam się z mjqxxxx.

— domotorp

2

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$

— Marzio De Biasi
źródło

Myślę, że ten problem jest dość oparty na TM, ale oczywiście nie można narysować linii.

— domotorp

Aby doprecyzować komentarz domotorp, powiedziałbym, że fakt, iż musi on w ogóle odwoływać się do pojęcia maszyny Turinga w opisie problemu, wyklucza go jako „naturalny problem związany z liczbami naturalnymi”. (Jeśli przypuszczamy, że problemem nienauralnym dotyczącym liczb naturalnych jest ten, którego ogólny format byłby zgodny np. Z Fermatem, który go studiował, nie zakładając

— zbytniefaktycznej

2

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$

— Igor Pak
źródło

Myślę, że jest to bardziej naturalne niż Manders-Adleman. Czy możliwe jest podanie mniej niż zmiennych i przykładów nierówności?

5

$5$

10

$10$

— T ....

Nie, 5 zmiennych jest najmniejszych. 10 - nie jestem pewien. Ale tak naprawdę nie możesz mieć mniej niż 6 ...

— Igor Pak

Czy istnieje powód i ? Znaczy to, że udowodniono, że wszystkie i skończona liczba nierówności w (również wszystkie zmienne i nierówności preparat jest w ?)?

\geq 5

$\geq5$

\geq 6

$\geq6$

\leq 4

$\leq4$

P

$P$

\leq 5

$\leq5$

\leq 5

$\leq5$

P

$P$

— T ....

Tak. W przypadku mniejszej liczby zmiennych problem występuje w P.

— Igor Pak

2

Tak. Wszystko jest w naszej pracy i pracy Danny'ego Nguyena. math.ucla.edu/~pak/papers/Nguyen-thesis.pdf

— Igor Pak

1

Co z problemem PARTYCJI ?

— Kevin A. Wortman
źródło

3

Nie, ponieważ dane wejściowe nie są liczbą, ale zbiorem.

— domotorp

1

Pytasz więc o problemy, dla których instancja jest dokładnie jedną liczbą naturalną? Nie sądzę, żeby było to jasne w twoim pytaniu, ponieważ pytasz o „problemy z naturalnymi danymi wejściowymi”, a twój przykład gry Nim obejmuje cztery liczby.

— Kevin A. Wortman

Przepraszam, jeśli byłem niejasny w sformułowaniu pytania.

— domotorp