Co-NP-kompletność minimalnej trasy TSP?

Ten problem pojawił się w moim niedawnym poście na blogu , przypuśćmy, że masz wycieczkę po TSP, czy jest to zgodne z NP-kompletnym, aby ustalić, czy jest to minimalne?

Dokładniej jest następujący problem NP-zupełny:

Instancja: Biorąc pod uwagę pełny wykres G z krawędziami ważonymi dodatnimi liczbami całkowitymi i prosty cykl C, który odwiedza wszystkie węzły G.

Pytanie: Czy istnieje prosty cykl D, który odwiedza wszystkie węzły G w taki sposób, że całkowity ciężar wszystkich krawędzi D w G jest ściśle mniejszy niż całkowity ciężar wszystkich krawędzi C w G?

Szkic możliwej redukcji, aby udowodnić, że jest kompletny NP.

Nieformalnie zaczyna się od zmodyfikowanej formuły 3SAT służącej do wykazania, że ​​3SAT jest kompletny z ASP (inny problem z rozwiązaniem) i „podąża” za standardowym łańcuchem redukcji 3SAT => BEZPOŚREDNI HAMCYCLE => BEZPOŚREDNI HAMCYCLE => TSP

• Start z wzorem 3SAT $\varphi$ z $n$ zmiennych $x_1,...x_n$ i $m$ caluses $C_1,...,C_m$ ;
• Trasformuj go do nowej formuły $\varphi'$ dodając nową zmienną $t$ ...;
• ... i rozszerzenie każdej klauzuli do ( x i 1 ∨ x i 2 ∨ x i 3 ∨ t ) ;$(x_{i_1} \lor x_{i_2} \lor x_{i_3})$$(x_{i_1} \lor x_{i_2} \lor x_{i_3} \lor t)$
• Od budowydiamenty strukturawykres G = { V , E } celu udowodnienia, że DIRECTED Hamiltona cykl jest NP-zupełny; przypuszczać, że każdy punkt C J odpowiadają węzła N J w G ;$\varphi'$$G = \{V,E\}$$C_j$$N_j$$G$
• Zmodyfikuj na wykres G ′ = { V ′ , E ′ }, zastępując każdy węzeł trzema połączonymi węzłami i zmodyfikuj krawędzie zgodnie ze standardową redukcją zastosowaną w celu wykazania kompletności NP NIEZRÓŻNIONEGO CYKLU HAMILTONIANOWEGO z BEZPOŚREDNIEGO HAMILTONIAŃSKIEGO CYCLE tj. jest węzłem używanym do krawędzi przychodzących, jest węzłem używanym do krawędzi wychodzących;$G$$G' = \{V',E'\}$u 1 , u 2 , u 3 u 1 u $u$$u_1, u_2, u_3$$u_1$$u_3$
• Przekształć instancję NIEZBĘDNEGO CYKLU HAMILTONIAJSKIEGO na na instancję TSP w której wszystkie krawędzie mają wagę , z wyjątkiem (unikalnej) krawędzi diamentu przechodzącej na "dodatnie" przypisanie które ma masę (czerwona krawędź na poniższym rysunku); wreszcie krawędzie dodane w celu uzupełnienia mają ciężar . T G ′ w = 1 t w = 2 G ′ w = $G'$$T$$G'$$w = 1$$t$$w = 2$$G'$$w = 3$

Oczywiście instancja TSP ma prosty cykl, który odwiedza wszystkie węzły, co odpowiada zadowalającemu przypisaniu w którym (i ta trasa może być łatwo skonstruowana w czasie wielomianowym), ale ma całkowitą wagę (ponieważ używa krawędzi odpowiadającej przypisaniu która ma wagę 2). ma kolejny prosty cykl, który odwiedza wszystkie węzły o niższej masie całkowitejwtedy i tylko wtedy, gdy nie stosuje się krawędzi ciężaru która odpowiada przypisaniu ; lub równoważnie wtedy i tylko wtedy, gdy istnieje inne zadowalające przypisanieφ ′ t = t r u e | V ′ | + 1 t = t r u e T | V ′ | 2 t = t r u e φ ′ t = f a l s e $T$$\varphi'$$t = true$$|V'|+1$$t = true$$T$$|V'|$$2$$t = true$$\varphi'$w którym ; ale może to być prawdą tylko wtedy, gdy oryginalna formuła jest zadowalająca.$t = false$$\varphi$

Zastanowię się więcej i napiszę formalny dowód (jeśli nie okaże się, że jest źle :-). Daj mi znać, jeśli potrzebujesz dodatkowych informacji na temat jednego lub więcej powyższych fragmentów.

Jak zauważył domotorp, interesującą konsekwencją jest to, że następujący problem jest NP-zupełny: Czy biorąc pod uwagę wykres i ścieżkę hamiltonowską, ma cykl hamiltonowski?$G$$G$

Papadimitriou i Steiglitz (1977) wykazali zupełność NP tego problemu.