Trudne problemy z rozszerzalnością

W przypadku problemu z rozszerzeniem otrzymujemy część rozwiązania i chcemy zdecydować, czy możemy go rozszerzyć do kompletnego rozwiązania. Niektóre problemy związane z rozszerzalnością można skutecznie rozwiązać, podczas gdy inne problemy z możliwością rozbudowy przekształcają problem łatwy w trudny.

Na przykład twierdzenie Koniga-Halla stwierdza, że wszystkie sześcienne dwustronne wykresy można pokolorować na 3 krawędziach, ale wersja rozszerzalności staje się kompletna, $NP$ jeśli otrzymamy kolory niektórych krawędzi.

Szukam pracy ankietowej dotyczącej problemów z twardą rozszerzalnością, w których problem podstawowy jest łatwy (lub trywialny jak w powyższym przykładzie).

cc.complexity-theory reference-request graph-theory np-hardness Mohammad Al-Turkistany
źródło

Nie wiem, czy istnieje ankieta dotycząca problemów z rozszerzalnością, ale przynajmniej jednym bardzo dobrze zbadanym takim problemem jest rozszerzenie wstępnego kolorowania . Znajdziesz wiele trafień szukających nazwy problemu.

Juho

Dwie uwagi: 1) czy istnieją problemy NPC, których nie można przekształcić w trudny problem z możliwością rozszerzenia? 2) Myślę, że bardzo interesująca byłaby także ankieta, która koncentruje się tylko na problemach z rozszerzalnością, dla których problem „podstawowy” ma nieznaną złożoność (np. Problem bez monochromatycznego prostokąta lub niektóre gry logiczne)

Marzio De Biasi

@MarzioDeBiasi Bardzo interesujący komentarz. 1) Nie znam takiego przykładu. 2) GI jest dobrym kandydatem i myślę, że jego problem z rozszerzalnością jest NP-zupełny.

Mohammad Al-Turkistany

Rozszerzona wersja problemów NP-trudnych to NP-hard (chciwie szukaj certyfikatu za pomocą wyroczni).

Kaveh

@MarzioDeBiasi: Rozszerzalność GI jest w rzeczywistości kompletna dla GI (nie tylko trudna dla GI, co moim zdaniem jest tym, co chciałeś powiedzieć), a zatem nie jest NP-pełna, chyba że PH się załamie. Rozszerzalność GI można przeformułować jako GI w kolorze wierzchołków (gdzie wierzchołki danego koloru mogą mapować tylko do wierzchołków tego samego koloru), co redukuje się do GI na wiele sposobów (jednym z nich jest dołączanie gadżetów do wierzchołków, podobnie według Twojego pomysłu ).

K_{n}

$K_n$

Joshua Grochow

n-kolorowanie wykresu nxn Sudoku jest banalne, ale jeśli niektóre kolory zostaną ci podane (wersja z możliwością rozszerzenia), stanie się NP-zupełne.

Przez „wykres Sudoku” mam na myśli naturalny wykres, którego powiązanym problemem kolorystycznym jest Sudoku. Załóżmy, że jest kwadratem. Wykres będzie miał wierzchołków, które oznaczymy jako dla . Dla każdej stałej wierzchołki tworzą klikę; dla każdej stałej wierzchołki tworzą klikę; i dla każdej stałej wierzchołki tworzą klikę. $n=k^2$ $n^2$ $(r_1, r_2; c_1, c_2)$ $r_1,r_2,c_1,c_2 \in [k] = [\sqrt{n}]$ $(r_1,r_2)$ $(r_1, r_2; *, *)$ $n$ $(c_1, c_2)$ $(*, *; c_1, c_2)$ $n$ $(r_1, c_1)$ $(r_1, *; c_1, *)$ $n$

Joshua Grochow
źródło

Trudne problemy z rozszerzalnością

Odpowiedzi: