Pytania otagowane jako complexity-classes

Klasy złożoności obliczeniowej i ich relacje

3
Twardość aproksymacji - błąd addytywny
Istnieje bogata literatura i co najmniej jedna bardzo dobra książka określająca znaną twardość wyników przybliżenia dla problemów trudnych dla NP w kontekście błędu multiplikatywnego (np. 2-przybliżenie dla pokrywy wierzchołków jest optymalne przy założeniu UGC). Obejmuje to również dobrze zrozumiałe klasy złożoności aproksymacji, takie jak APX, PTAS i tak dalej. Co …
3
Jakie są relacje między tymi hipotezami w teorii drobnoziarnistej złożoności?
Teoria złożoności, poprzez takie koncepcje jak kompletność NP, rozróżnia problemy obliczeniowe, które mają względnie skuteczne rozwiązania, i te, które są trudne do rozwiązania. Złożoność „drobnoziarnista” ma na celu dopracowanie tego jakościowego rozróżnienia w ilościowy przewodnik co do dokładnego czasu potrzebnego na rozwiązanie problemów. Więcej informacji można znaleźć tutaj: http://simons.berkeley.edu/programs/complexity2015 Oto …
3
Problemy z optymalizacją przy dobrej charakterystyce, ale bez algorytmu czasu wielomianowego
Rozważ problemy z optymalizacją w poniższym formularzu. Niech f(x)f(x)f(x) będzie funkcją obliczalną w czasie wielomianowym, która odwzorowuje ciąg xxx na liczbę wymierną. Problem optymalizacji jest następujący: jaka jest maksymalna wartość f(x)f(x)f(x) ponad nnn bitowych ciągów xxx ? gggmaxxf(x)=minyg(y)maxxf(x)=minyg(y)\max_x f(x) = \min_y g(y)xxxnnnyyymmmnnnmmm Wiele naturalnych i ważnych problemów związanych z optymalizacją …
1
Tardos Funkcja kontrprzykład do Bluma
W tym wątku próba próby Norbet Bluma jest zwięźle obalona przez odnotowanie, że funkcja Tardos jest przeciwne do Twierdzenia 6.P.≠ N.P.P≠NPP \neq NP Twierdzenie 6 : Niech będzie dowolną monotoniczną funkcją boolowską. Załóżmy, że istnieje aproksymator A CNF-DNF, którego można użyć do udowodnienia dolnej granicy C m ( f ) …
3
Problemy poza P, które nie są P-trudne
Czytając odpowiedź Petera Shora i wcześniejsze pytanie Adama Crume'a, zdałem sobie sprawę, że mam pewne nieporozumienia na temat tego, co to znaczy być PP\mathsf{P} twardym. Problemem jest PP\mathsf{P} -hard jeśli jakiś problem w PP\mathsf{P} sprowadza się do niego z LL\mathsf{L} (lub jeśli wolisz NCNC\mathsf{NC} ) obniżek. Problem występuje poza PP\mathsf{P} …
3
Czy wpisane obliczenia lambda wyrażają * wszystkie * algorytmy poniżej określonej złożoności?
Wiem, że złożoność większości odmian kalkulatorów lambda bez prymitywu kombinatora Y jest ograniczona, tzn. Można wyrazić tylko funkcje o ograniczonej złożoności, przy czym granica staje się większa wraz ze wzrostem ekspresyjności systemu typów. Pamiętam, że np. Rachunek konstrukcji może wyrażać co najwyżej podwójnie wykładniczą złożoność. Moje pytanie dotyczy tego, czy …
1
Czy P jest równe przecięciu wszystkich wielobiegunowych klas czasowych?
Nazwijmy funkcję wielobiegunową, jeśli dla każdego c> 0 .f(n)f(n)f(n) c > 0limn→∞nc/f(n)=0limn→∞nc/f(n)=0\lim_{n\rightarrow\infty} n^c/f(n)=0c>0c>0c>0 Oczywiste jest, że dla każdego języka L∈PL∈PL\in {\mathsf P} utrzymuje, że L∈DTIME(f(n))L∈DTIME(f(n))L\in {\mathsf {DTIME}}(f(n)) dla każdego superminomalnego ograniczenia czasowego f(n)f(n)f(n) . Zastanawiam się, czy odwrotność tego stwierdzenia jest również prawdą? To znaczy, jeśli znamy L∈DTIME(f(n))L∈DTIME(f(n))L\in {\mathsf {DTIME}}(f(n)) …
3
Ograniczenia przetwarzania równoległego
Jestem ciekawy w szerokim znaczeniu tego, co wiadomo na temat algorytmów równoległych w P. Znalazłem następujący artykuł w Wikipedii na ten temat: http://en.wikipedia.org/wiki/NC_%28complexity%29 Artykuł zawiera następujące zdanie: Nie wiadomo, czy NC = P, ale większość badaczy podejrzewa, że ​​jest to fałsz, co oznacza, że ​​prawdopodobnie istnieją pewne możliwe do rozwiązania …
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.