Czy możemy zdecydować, czy stały ma unikalny termin?

Załóżmy, że otrzymujemy macierz n przez n, M, z wpisami liczb całkowitych. Czy możemy zdecydować w P, czy istnieje permutacja$\sigma$ taka, że ​​dla wszystkich permutacji mamy ?$\pi\ne\sigma$$\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)}$

Uwagi Oczywiście można wymienić produkt na sumę, problem pozostaje ten sam.

Jeśli macierz może mieć tylko wpisy 0/1, to otrzymujemy problem Bipartite-UPM, który występuje nawet w NC.

Edycja: Podjęcie decyzji, czy najmniejszy termin jest unikalny, jest trudne, jeśli pozwolimy na losowe redukcje. Tak naprawdę pierwotnie chciałem zadać to pytanie, ponieważ pomogłoby to rozwiązać ten jeden. Teraz okazało się, że to jest NP-zupełny, więc pozwól mi szkic redukcji do naszego problemu. Wyobraź sobie, że wejście jest macierzą zero-jedynkową (możemy przypuszczać, że) i zamień wpisy zerowe na losowe liczby rzeczywiste od 2 do 2 + 1 / n. Teraz w tej nowej matrycy z dużym prawdopodobieństwem najmniejszy termin jest unikalny tylko wtedy, gdy oryginalna matryca jest dopuszczalna w formie trójkąta górnego.

Edycja: Podobne pytania:

Czy na wykresie ważonym na krawędzi jest cykl Hamiltona o wyjątkowej wadze?

Jeśli mamy CNF z wagami przypisanymi do każdej zmiennej / spełniającego przyporządkowanie, to czy istnieje unikalne przyporządkowanie wagowe?

Są to oczywiście co najmniej trudne NP. Czy te problemy są równoważne z oryginałem, czy są trudniejsze?

Niezły problem! Nietrudno jest przedstawić redukcję pokazującą, że jeśli ktoś może rozwiązać problem, to może również rozwiązać następujący problem, nazwać go SUMĄ PODSETOWANĄ:

Biorąc pod uwagę liczby całkowite ₁ , ..., _n , istnieje podzbiór S _ai , którego suma nie jest dzielona przez żaden inny podzbiór?

Redukcja polega na zmniejszeniu najpierw ISOLATED SUBSET SUM do ISOLATED PERFECT MATCHING, gdzie mając na uwadze ważony dwustronny wykres G, chcemy znaleźć idealne dopasowanie, którego waga nie jest dzielona przez żadne inne idealne dopasowanie. Redukcja ta jest prosta: dla każdego i utwórz 2x2 kompletny podgrafu G _I w G, w taki sposób, który z dwóch możliwych skojarzeń możemy wybrać dla G _i koduje nasz wybór, czy dana _I jest w zbiorze S.

Następnie zmniejsz ISOLATED PERFECT MATCHING do swojego problemu w następujący sposób:

1. Dla wszystkich i, j, jeśli krawędź (i, j) istnieje i ma wagę w _ij , to ustaw M _ij : = exp (w _ij ). (To zamienia sumy w produkty.)
2. Dla wszystkich i, j, jeśli krawędź (i, j) nie istnieje, ustaw M _ij : = 0.
3. Pad M, aby upewnić się, że istnieją dwie lub więcej permutacje π takie, że Π M _{i, π (i)} = 0. (Wyklucza to fałszywe rozwiązania, które nie odpowiadają żadnemu idealnemu dopasowaniu w G.)

Teraz ISOLATED SUBSET SUM z pewnością wydaje się być co najmniej NP-trudny, a może nawet trudniejszy (oczywista górna granica to tylko P ₂ P)! Co więcej, być może można by udowodnić, że SUMA PODZESPOŁU IZOLOWANEGO jest NP-trudna przy użyciu losowej redukcji w stylu Valiant-Vazirani. Jest to jednak wyzwanie, które pozostawiam komuś innemu ...