Czy jakiś skończony problem może występować w NP-Complete?

Mój wykładowca wydał oświadczenie

Jakikolwiek problem skończony nie może być NP-Complete

Mówił wtedy o Sudoku, mówiąc coś w stylu, że dla Sudoku 8x8 istnieje skończony zestaw rozwiązań, ale nie pamiętam dokładnie, co powiedział. Zapisałem notatkę, którą zacytowałem, ale nadal nie rozumiem.

Sudoku są NP kompletne, jeśli się nie mylę. Problem kliki jest również NP-Complete, a gdybym miał problem 4-Clique, czy nie jest to problem skończony, który jest NP-Complete?

np-complete np TheRapture87
źródło

Co to jest „skończony problem”? Google i Wikipedia nie pomagają.

Anton Trunov

@AntonTrunov Problem polegający na ograniczeniu długości danych wejściowych.

Yuval Filmus

@YuvalFilmus, Czy to nie prawda o wszystkich prawidłowych parach wejściowych maszyny Turinga *? IIRC jeden z symboli jest oznaczony pustym symbolem, a wejście początkowo ma ograniczony obszar, poza którym nie mogą się pojawiać inne symbole niż pusty symbol. Termin „NP zakończony” zwykle nie jest używany w kontekście operacji na strumieniach, których nie można modelować bez rozluźnienia tego założenia.

Mike Samuel

@MikeSamuel Kiedy mówię o ograniczonej długości, mam na myśli wejście wielkości co najwyżej 100. (Lub dowolnej liczby innej niż 100.)

Yuval Filmus

@YuvalFilmus, ok. Mówię, termin „NP zakończony” jest używany tylko wtedy, gdy na wejściu nie ma żadnych niepustych symboli lub istnieje liczba całkowita, która jest liczbą symboli między lewym niepustym symbolem a skrajnym prawym niepustym symbolem . 100 byłoby takim przykładem.

Mike Samuel

Odpowiedzi:

Jeśli problem skończony jest NP-zupełny, to P = NP, ponieważ każdy problem skończony ma algorytm wielomianowy (nawet algorytm stały).

Kiedy mówimy, że Sudoku jest kompletne z NP, mamy na myśli, że uogólniona wersja Sudoku rozgrywana na planszy jest kompletna z NP. $n^2 \times n^2$

Wreszcie problem z 4 klikami, choć nie jest problemem skończonym (wykres wejściowy ma nieograniczony rozmiar), jest łatwym problemem z algorytmem wielomianowym.

Yuval Filmus
źródło

Więc jest problem 4-kliki P, ponieważ ma on algorytm wielomianowy?

TheRapture87

@ Aceboy1993 Tak, to jest definicja P.

Yuval Filmus

Ale dlaczego uważa się, że K-klika jest w NP-Complete? Czy K nie reprezentuje tylko liczby takiej jak 4?

TheRapture87

@ Aceboy1993 Nie, jest częścią danych wejściowych. Dla stałego problem występuje w P.

k

$k$

k

$k$

Yuval Filmus

Możemy również udowodnić, że Clique jest NP-kompletny.

Yuval Filmus

Oświadczenie twojego nauczyciela jest nieprawidłowe lub prawdopodobnie nie słyszałeś go poprawnie. Prawidłowe stwierdzenie to

$L$ $|L| \geq 1$ $P = NP$

$P \neq NP$ $|L|>1$ $\emptyset$ $P=NP$ $P \neq NP$

Sudoku lub szachy nie są kompletne NP (jak zauważył Yuval), ponieważ ich wkładem jest skończona tablica 9x9 lub 8x8 (mówię o wersjach decyzyjnych, czy sudoku ma rozwiązanie, czy szachy ma strategię wygrywającą). W szachach zakładam, że jeśli powtórzysz pozycję, uznaje się to za remis.

Shreesh
źródło

Przypomnij: Problem X jest NP-zupełny, jeśli spełnia dwa kryteria:

a) Jest w NP - tzn. każde odgadnięte rozwiązanie X można zweryfikować w czasie wielomianowym.

b) Jest kompletny dla NP - Tj. Każdy problem Y w NP ma redukcję czasu wielomianowego, co przekłada instancję Y na instancję X (tak, że każdy program czasu wielomianowego, który rozwiązuje X, również rozwiązałby Y w czasie wielomianowym ).

Możemy zgodzić się, że Sudoku 9x9 spełnia wymagania (a). To (b) upadek rzeczy. Mówiąc bardziej ogólnie - problemy (w NP lub inne) zazwyczaj mają instancje o rozmiarze N dla dowolnie dużych wartości N ; z pewnością dotyczy to znanych problemów w NP. Zmniejszenie z takiego problemu do takiego, który ma maksymalny możliwy rozmiar problemu, nie mogłoby być poprawnym zmniejszeniem liczby przypadków między instancjami, ponieważ to pierwsze zawsze ma (nieskończenie) więcej wystąpień niż drugie. Dlatego Sudoku należy uogólnić na macierze NxN, zanim będzie można rozważyć kompletność NP.

PMar
źródło

To nie jest poprawne. Zupełnie możliwe jest prawidłowe ograniczenie problemu z nieskończenie wieloma instancjami do problemu z nieskończenie wieloma instancjami. Na przykład tutaj jest redukcja z SAT do problemu określania, czy łańcuch długości 1 jest równy „a”: jeśli instancja SAT jest zadowalająca, zamapuj ją na łańcuch „a”; w przeciwnym razie zamapuj go na ciąg „b”. Otóż, ta redukcja (prawdopodobnie) nie jest obliczalna w czasie wielomianowym, ale jest to całkowicie poprawna redukcja.

David Richerby