Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

7
Dla jakich problemów w P łatwiej jest zweryfikować wynik niż go znaleźć?
W przypadku (wyszukiwania wersji) problemów z NP zakończonych weryfikacja rozwiązania jest wyraźnie łatwiejsza niż znalezienie, ponieważ weryfikacja może być przeprowadzona w czasie wielomianowym, podczas gdy znalezienie świadka zajmuje (prawdopodobnie) wykładniczy czas. Jednak w P rozwiązanie można znaleźć również w czasie wielomianowym, więc nie wydaje się oczywiste, kiedy weryfikacja jest szybsza …
4
Dlaczego traktujemy log-space jako model wydajnego obliczania (zamiast polilog-space)?
To może być pytanie subiektywne, a nie konkretne, ale tak czy inaczej. W teorii złożoności badamy pojęcie wydajnych obliczeń. Istnieją klasy takie jak oznacza czas wielomianowy , a L oznacza miejsce na log . Oba są uważane za reprezentowane jako rodzaj „wydajności” i dość dobrze wychwytują trudności niektórych problemów.PP\mathsf{P}LL\mathsf{L} Istnieje …
6
Sposoby, aby matematyk był informowany o bieżących badaniach w teorii złożoności
Teoria złożoności jest moim drugorzędnym zainteresowaniem, ale nie jest moim głównym zainteresowaniem badawczym, więc nie mam nadziei, że wezmę udział we wszystkich konferencjach, przeczytam wszystkie blogi i upewnię się, że „w” tłumie cc: ja na każdym gorące wiadomości. Próbuję to zrobić, ale zastanawiam się, jakie metody przyniosą mi największe zyski …
20
Trudne problemy z NP na drzewach
Kilka problemów optymalizacyjnych, o których wiadomo, że są trudne do NP na grafach ogólnych, można w prosty sposób rozwiązać w czasie wielomianowym (niektóre nawet w czasie liniowym), gdy grafem wejściowym jest drzewo. Przykłady obejmują minimalną osłonę wierzchołków, maksymalny niezależny zestaw, izomorfizm subgrafu. Wymień niektóre naturalne problemy z optymalizacją, które na …
4
Jakie są konsekwencje
Wiemy, że L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} i że L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , gdzie L2=DSPACE(log2n)L2=DSPACE(log2⁡n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . Wiadomo również, że polyL≠PpolyL≠P\mathsf{polyL} \neq \mathsf{P}ponieważ ten drugi ma całkowite problemy w przestrzeni logarytmicznej, wielokrotne redukcje jeden-jedynki, podczas gdy ten drugi nie (ze względu na twierdzenie o …
5
Czy w teorii złożoności istnieją prawa ochrony?
Zacznę od kilku przykładów. Dlaczego tak trywialne jest pokazanie, że CVP jest w P, ale tak trudno jest pokazać LP w P; podczas gdy oba są problemami typu P-zupełnego. Lub weźmy pierwszeństwo. Łatwiej jest wyświetlać kompozyty w NP niż liczby pierwsze w NP (co wymagało Pratta) i ostatecznie w P. …
3
Kompletny wariant faktoringu NP.
Książka Arory i Baraka przedstawia faktoring jako następujący problem: FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\} Dodają, w dalszej części rozdziału 2, że usunięcie faktu, że jest liczbą pierwszą, sprawia, że …
4
Uogólnione twierdzenie Ladnera
Twierdzenie Ladnera stwierdza, że ​​jeśli P ≠ NP, to istnieje nieskończona hierarchia klas złożoności ściśle zawierających P i ściśle zawartych w NP. Dowód wykorzystuje kompletność SAT przy wielu redukcjach NP. Hierarchia zawiera klasy złożoności skonstruowane przez rodzaj diagonalizacji, z których każda zawiera pewien język, do którego języków w niższych klasach …
5
Czy hierarchia Chomsky'ego jest przestarzała?
Hierarchia Chomsky'ego (–Schützenberger) jest używana w podręcznikach teoretycznej informatyki, ale oczywiście obejmuje tylko bardzo niewielką część języków formalnych (REG, CFL, CSL, RE) w porównaniu z pełnym diagramem złożoności Zoo . Czy hierarchia odgrywa już jakąkolwiek rolę w bieżących badaniach? Znalazłem niewiele odniesień do Chomsky'ego tutaj na cstheory.stackexchange, aw Zoo Złożoności …
8
Nekrologi martwych przypuszczeń
Szukam domysłów na temat algorytmów i złożoności, które przez pewien czas były postrzegane przez wielu jako wiarygodne, ale później zostały one obalone lub przynajmniej niewiary, z powodu narastających kontr-dowodów. Oto dwa przykłady: Hipoteza o losowej wyroczni: relacje między klasami złożoności, które dotyczą prawie wszystkich relatywizowanych światów, dotyczą również przypadku nie …
4
Algorytmy aproksymacyjne dla metrycznego TSP
Wiadomo, że metryczny TSP może być przybliżony w granicach i nie może być przybliżony lepiej niż 1231.51.51.5 w czasie wielomianowym. Czy coś wiadomo na temat znajdowania rozwiązań aproksymacyjnych w czasie wykładniczym (na przykład mniej niż2nkroków z tylko przestrzenią wielomianową)? Np. W jakim czasie i przestrzeni możemy znaleźć trasę, której odległość …
10
Zastosowania złożoności Kołmogorowa w złożoności obliczeniowej
Nieformalnie mówiąc, złożoność Kołmogorowa ciągu jest długością najkrótszego programu, który wypisuje . Możemy zdefiniować pojęcie „losowego ciągu” używając go ( jest losowy, jeśli ) Łatwo jest zauważyć, że większość ciągów jest losowa (nie ma tak wielu krótkich programów).x x K ( x ) ≥ 0,99 | x |xxxxxxxxxK.( x ) …
8
Znaczenie luki w integralności
Zawsze miałem problem ze zrozumieniem znaczenia luki integralności (IG) i ją ograniczam. IG jest stosunkiem (jakości) optymalnej liczby całkowitej do (jakości) optymalnego rzeczywistego rozwiązania złagodzenia problemu. Rozważmy przykrycie wierzchołków (VC) jako przykład. VC można określić jako znalezienie optymalnego rozwiązania liczb całkowitych następującego zestawu równań liniowych: Mamy zero / jednego o …
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.