Pytania otagowane jako complexity-theory

Pytania związane z (obliczeniową) złożonością rozwiązywania problemów

2
Dowód sprzeczności dla nierówności P i NP?
Próbuję argumentować, że N nie jest równe NP przy użyciu twierdzeń hierarchicznych. To mój argument, ale kiedy pokazałem go naszemu nauczycielowi i po dedukcji powiedział, że jest to problematyczne, gdy nie mogę znaleźć ważnego powodu do zaakceptowania. Zaczynamy od założenia, że . Następnie zwraca który następnie następuje po tym . …
1
Analiza złożoności algorytmu dla implementacji funkcjonalnego języka programowania
Dowiedziałem się dzisiaj, że analiza algorytmów różni się w zależności od modelu obliczeniowego. To jest coś, o czym nigdy nie myślałem ani nie słyszałem. Przykładem podanym mi przez użytkownika @chi , który dalej to ilustruje : Np. Rozważ zadanie: dany zwraca x i . W pamięci RAM można to rozwiązać …
2
Złożoność znalezienia piłki, która maksymalizuje liczbę leżących w niej punktów
Biorąc pod uwagę zbiór punktów x1,…,xn∈R2x1,…,xn∈R2x_1, \ldots, x_n \in \mathbb{R}^2 i promień . Co jest złożonością znalezienia punktu o większej liczbie punktów w odległości mniejszej niż . Np. Ten, który maksymalizuje ?rrrrrr∑ni=11∥x−xi∥≤r∑i=1n1‖x−xi‖≤r\sum_{i=1}^n \mathbb{1}_{\|x - x_i\| \leq r} Algorytm brutalnej siły polegałby na przejściu każdego punktu i zliczeniu liczby punktów znajdujących …
1
Jeśli
Jeśli P.=NPP=NP\mathbf{P} = \mathbf{NP} , to czy L =NLL=NL.\mathbf{L} = \mathbf{NL} ? Zadaję to pytanie, ponieważ dla innych niedeterministycznych klas wydaje się, że P = N PP=NP.\mathbf{P} = \mathbf{NP} zawsze ustala, że ​​są one równe ich deterministycznym odpowiednikom.
1
Czy kompletne zestawy NP są tworzone z dwóch innych zestawów tylko wtedy, gdy co najmniej jeden jest twardy NP?
To pytanie jest nieco odwrotne do poprzedniego pytania dotyczącego zestawów utworzonych z operacji na zestawach na zestawach NP-complete: Jeśli zbiór wynikający ze związku, przecięcia lub iloczynu kartezjańskiego dwóch rozstrzygalnych zbiorów L1L1L_1 i jest NP-kompletny, to czy przynajmniej jeden z koniecznie NP-twardy? Wiem, że oba nie mogą być w P (zakładając, …
4
Czy znalezienie świadka może być trudne, nawet jeśli już wiemy, że istnieje?
Typowe przykłady problemów trudnych dla NP (klika, 3-SAT, osłona wierzchołków itp.) Są tego typu, w którym nie wiemy, czy odpowiedź brzmi „tak” czy „nie” wcześniej. Załóżmy, że mamy problem, w którym wiemy, że odpowiedź brzmi tak, a ponadto możemy zweryfikować świadka w czasie wielomianowym. Czy wtedy zawsze możemy znaleźć świadka …
2
Czy
Jeśli hierarchia zapada się na swój drugi poziom (według twierdzenia Karpa-Liptona). Ale co z N P i C o N P ?RP=NPRP=NP\sf RP = NPNPNP\sf NPcoNPcoNP\sf coNP Starałem się udowodnić, że zawarty jest w N P (drugi kierunek jest trywialne, jeśli R P = N P ), ale bez skutku, …
2
Czy ta klasyczna gra z układankami NP-zupełna?
Istnieje klasyczna gra logiczna, bardzo podobna do krzyżówki, z tą różnicą, że podana jest lista słów, a następnie podana jest kwadratowa tablica złożona z kwadratów jednostkowych, z niektórymi kwadratami zaciemnionymi jak krzyżówka, a na niektórych kwadratach jest już napisany list. Celem jest zapisanie każdego słowa z listy raz i tylko …
4
Odzyskiwanie punktu osadzania z wykresu z krawędziami ważonymi odległością punktu
Załóżmy, że podam ci niekierowany wykres z ważonymi krawędziami i powiem, że każdy węzeł odpowiada punktowi w przestrzeni 3D. Ilekroć pomiędzy dwoma węzłami jest krawędź, ciężar krawędzi jest odległością między punktami. Twoim celem jest zrekonstruowanie względnych pozycji punktów, biorąc pod uwagę tylko dostępne odległości (reprezentowane przez wagi krawędzi). Na przykład, …
1
Jak wyglądają klasy złożoności, jeśli zastosujemy redukcje Turinga?
Do rozumowania takich rzeczy, jak kompletność NP, zwykle stosujemy redukcje wielokrotne jeden (tj. Redukcje Karp). Prowadzi to do takich zdjęć: (zgodnie ze standardowymi przypuszczeniami). Jestem pewien, że wszyscy znamy tego rodzaju rzeczy. Jakie otrzymamy zdjęcie, jeśli będziemy pracować z redukcjami Turinga (tj. Redukcjami Cooka)? Jak zmienia się obraz? PNPPNPP^{NP}NPNPNPcoNPcoNPcoNPPNPPNPP^{NP}NPNPNP P⊂PNP⊂PH⊂PSPACEP⊂PNP⊂PH⊂PSPACEP …
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.