Pytania otagowane jako reductions

Redukcja polega na przekształceniu jednego problemu w inny. Przykładem zastosowania redukcji byłoby pokazanie, czy problem P jest nierozstrzygalny. Można to osiągnąć poprzez przekształcenie lub wykonanie redukcji problemu decyzyjnego w problem nierozstrzygalny. Jeśli można to osiągnąć, wykazaliśmy, że problem P jest nierozstrzygalny. P.

1
Czy istnieje lista problemów kanonicznych w systemach rozproszonych?
W ubiegłym tygodniu ponownie przeczytałem transkrypt Leslie Lamport z 1982 r. Z konferencji, którą wygłosił na temat Rozwiązanych problemów, Nierozwiązanych problemów i nieproblemów w współbieżności . Artykuł jest czytelny, ale jedną z rzeczy, które skłoniły mnie do myślenia, jest następujące stwierdzenie: Czy każdy problem można uznać za problem wzajemnego wykluczenia …
2
Czy PPAD naprawdę wychwytuje pojęcie znalezienia innego niezrównoważonego wierzchołka?
Klasa złożoności PPAD została wynaleziona przez Christosa Papadimitriou w jego przełomowym artykule z 1994 roku . Klasa ma na celu uchwycenie złożoności problemów wyszukiwania, w których istnienie rozwiązania jest gwarantowane przez „Argument parzystości w grafach ukierunkowanych”: jeśli w grafie ukierunkowanym występuje niewyważony wierzchołek, musi istnieć inny. Ale zazwyczaj klasa jest …
3
Czy istnieje ograniczenie do gier typu „drzwi i płyta dociskowa”, które nie eksplodują długości rozwiązania?
Ten dokument stanowi dowód, że w grze z drzwiami i płytkami dociskowymi trudno jest ustalić, czy awatar (gracza) może dotrzeć do danego miejsca. Dowodzi tego redukcja z TQBF , a długość powstałych rozwiązań zależy wykładniczo od liczby uniwersalnych kwantyfikatorów we wzorze. Czy istnieje redukcja z maszyny NPSPACE do takiej gry, …
3
Rachunek konstrukcji: skompresuj wyrażenie do jego najmniejszej postaci
Wiem, że Rachunek Konstrukcji jest silnie normalizujący, co oznacza, że ​​każde wyrażenie ma normalną wartość, która nie może być beta, a jeszcze bardziej zmniejszona eta. W rzeczywistości jest to najbardziej wydajne wyrażenie, które oblicza tę samą wartość, co oryginalne wyrażenie. Ale w niektórych przypadkach normalizacja może zredukować małe wyrażenie do …
2
Ograniczona liczba zmiennych wystąpień w SAT 1-w-3
Czy jest znany wynik dotyczący klasy złożoności 1-w-3-SAT z ograniczoną liczbą zmiennych zdarzeń? Wymyśliłem następującą oszczędną redukcję u Petera Nightingale'a, ale chcę zacytować coś, jeśli jest to znane. Oto sztuczka, którą wymyśliliśmy. To pokazuje, że 1-w-3-SAT ograniczony do 3 wystąpień na zmienną jest NP kompletny i #P zakończony (ponieważ 1-w-3-SAT …
1
Dlaczego problemy z uzupełnianiem NP nie mają podobnych współczynników aproksymacji?
Ponieważ 2 problemy NP-zupełne są z definicji redukowalne względem siebie, więc rozwiązanie jednego z nich można uzyskać za pomocą czarnej skrzynki rozwiązującej drugi, dlaczego nie mają podobnych współczynników aproksymacji (w odniesieniu do ich odpowiedników optymalizacyjnych )? Wydaje mi się, że pewne stałe lub nawet wielomianowe znoszenie może być zrozumiane, ale …
5
Wystąpienie redukcji FPT, która nie jest redukcją czasu wielomianowego
W sparametryzowanej złożoności ludzie używają redukcji stałych parametrów (FPT), aby udowodnić twardość W [t]. Teoretycznie redukcja FPT nie jest redukcją czasu wielomianowego, ponieważ może działać wykładniczo w parametrze k. Ale w praktyce wszystkie redukcje FPT, które widziałem, są redukcjami czasu p, co oznacza, że ​​dowody twardości W [t] prawie zawsze …
1
Na rzadkich kompletach i P vs L.
Twierdzenie Mahaneya mówi nam, że jeśli istnieje rzadki zestaw przy wielomianowych redukcjach wielokrotności jeden, to . (Patrz „ Rzadkie kompletne zestawy dla NP: Rozwiązanie przypuszczenia Bermana i Hartmanisa ”)NPNPNPP=NPP=NPP = NP Czy znane są konsekwencje istnienia rzadkich kompletnych zestawów dla innych klas złożoności? W szczególności, jeśli w obszarze logarytmicznym występuje …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.