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.

2
Trudne problemy z sumą pierwiastków kwadratowych?
Suma pierwiastki problemu prosi, ponieważ dwie sekwencje i dodatnich liczb całkowitych czy suma mniejszy, równy lub większy niż suma . Status złożoności tego problemu jest otwarty; zobacz ten post, aby uzyskać więcej informacji. Problem ten powstaje naturalnie w geometrii obliczeniowej, szczególnie w problemach związanych z najkrótszymi ścieżkami euklidesowymi, i stanowi …
3
Dlaczego losowość ma większy wpływ na redukcje niż na algorytmy?
Przypuszcza się, że losowość nie rozszerza potęgi algorytmów wielomianu czasowego, co oznacza, że jest przypuszczalny do utrzymania. Z drugiej strony losowość wydaje się mieć zupełnie inny wpływ na skrócenie czasu wielomianu . Według dobrze znanego wyniku Valiant i Vazirani, redukuje się do poprzez losowe wielomianowe skrócenie czasu. Jest mało prawdopodobne, …
2
Derandomizacja Valiant-Vazirani?
Twierdzenie Valiant-Vazirani mówi, że jeśli istnieje wielomianowy algorytm czasu (deterministyczny lub losowy) do rozróżniania między formułą SAT, która ma dokładnie jedno zadowalające przypisanie, a formułą niezadowalającą - wówczas NP = RP . Twierdzenie to zostało udowodnione poprzez wykazanie, że UNIQUE-SAT jest NP- twardy przy randomizowanych redukcjach. Z zastrzeżeniem prawdopodobnych przypuszczeń …
5
Szybka redukcja z RSA do SAT
Wpis na blogu Scotta Aaronsona przedstawił dziś listę interesujących otwartych problemów / zadań w złożoności. Jeden zwrócił moją uwagę: Zbuduj bibliotekę publiczną instancji 3SAT z jak najmniejszą liczbą zmiennych i klauzul, które mogłyby mieć godne uwagi konsekwencje, jeśli zostaną rozwiązane. (Na przykład, instancje kodujące wyzwania faktoringu RSA.) Zbadaj wydajność najlepszych …
7
Nietrywialne członkostwo w NP
Czy jest przykładem języka, który jest w NPNPNP , ale gdzie nie możemy udowodnić ten fakt bezpośrednio poprzez pokazanie, że istnieje wielomian świadka do członkostwa w tym języku? Zamiast tego fakt, że język znajduje się w NPNPNP , można udowodnić, redukując go do innego języka w NPNPNP , gdzie powiązanie …
27 reductions  np 
1
Czy znane są algorytmy podwykładnicze dla PLANAR SAT?
Niektóre problemy trudne NP, które są wykładnicze na grafach ogólnych, są sub wykładnicze na grafach płaskich, ponieważ szerokość wynosi co najwyżej i są wykładnicze w szerokości.4,9 | V.( G ) |------√4.9|V(G)|4.9 \sqrt{|V(G)|} Zasadniczo jestem zainteresowany, czy istnieją algorytmy podwykładnicze dla PLANAR SAT, który jest NP-zupełny. Niech być wzór nanowłókien węglowych …
2
Czy istnieje bezpośrednia / naturalna redukcja, aby liczyć niedwustronne idealne dopasowania za pomocą stałego?
Zliczanie liczby idealnych dopasowań na wykresie dwustronnym można natychmiast zredukować do obliczenia wartości stałej. Ponieważ znalezienie idealnego dopasowania na grafie dwustronnym występuje w NP, istnieje pewna redukcja z grafów dwustronnych do stałych, ale może to wiązać się z nieprzyjemnym wielomianowym powiększeniem poprzez zastosowanie redukcji Cooka do SAT, a następnie twierdzenia …
6
Zaawansowane techniki określania dolnych granic złożoności
Niektórzy z was mogli śledzić to pytanie , które zostało zamknięte z powodu braku poziomu badań. Wyciągam więc część pytania, która jest na poziomie badawczym. Oprócz „prostszych” technik, takich jak redukcja do sortowania lub problem z WYŁĄCZENIEM, jakie techniki zostały zastosowane, aby udowodnić dolne granice złożoności problemu w czasie? W …
2
Naturalna redukcja CLIQUE do k-Color
Widoczna jest redukcja z CLIQUE na k-Color, ponieważ oba są NP-Complete. W rzeczywistości mogę go zbudować, tworząc redukcję z CLIQUE do 3-SAT z redukcją z 3-SAT do k-Color. Zastanawiam się, czy istnieje rozsądna bezpośrednia redukcja między tymi problemami. Powiedzmy, redukcję, którą mógłbym wyjaśnić przyjacielowi dość krótko, bez potrzeby opisywania języka …
5
Ciekawy o komputerowych dowodach kompletności NP
W artykule „KOMPLEKSOWOŚĆ PROBLEMÓW Z ZADOWOLENIEM” Tomasza J. Schaefera autor wspomniał, że This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the relational complexity could be explored with the help of a computer. The computer would be …
1
Mnożenie binarne i splot parzystości
To pytanie dotyczy związku między normalnym mnożeniem liczb binarnych a wielomianowym mnożeniem mod 2. Aby uczynić pytanie konkretnym, idealnie chciałbym wiedzieć, czy istnieje lepsze rozwiązanie pytania z Knuth vol. 2, wydanie trzecie, strona 420 niż podano w książce. „Czy mnożenie wielomianów modulo 2 można ułatwić, stosując zwykłe operacje arytmetyczne na …
9
Redukcje z książki.
Jest to zgodne z „ Algorytmami z książki ”. Chociaż redukcje są również algorytmami, pomyślałem, że wątpliwe jest, aby pomyśleć o redukcji w odpowiedzi na pytanie o algorytmy z książki. Stąd osobne zapytanie! Wszelkie redukcje są mile widziane. Zacznę od bardzo prostej redukcji od osłony wierzchołków do multikutów na gwiazdach. …
3
Problemy, które są NP-zupełne w przypadku randomizacji lub redukcji P / poli.
W tym pytaniu wydaje się, że zidentyfikowaliśmy naturalny problem, który jest zupełny NP przy redukcjach losowych, ale być może nie przy redukcjach deterministycznych (chociaż zależy to od tego, które niesprawdzone założenia teorii liczb są prawdziwe). Czy znane są inne problemy? Czy istnieją jakieś naturalne problemy, które są NP-zupełne w przypadku …
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.