Pytania otagowane jako cc.complexity-theory

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

3
Czy istnieje prosta gra o asymetrycznej złożoności?
Rozważ pełną informację dla dwóch graczy w kombinatorycznych grach, które kończą się po wielomianowej liczbie ruchów, i naprzemiennie gracze wybierają z ograniczonej liczby dozwolonych ruchów. Zwykle pytanie brzmi, jak trudno jest powiedzieć zwycięzcy z danej pozycji. Innym byłoby to, jak trudno wybrać zwycięski ruch ze zwycięskiej pozycji. (Tutaj nazywam ruch …
2
Jak ocenić, czy definicja złożoności obliczeniowej rzeczywistych jest naturalna czy odpowiednia?
Jak wiemy, definicja złożoności obliczeniowej algorytmu prawie nie budzi kontrowersji, ale definicja złożoności obliczeniowej rzeczywistych lub modeli obliczeniowych rzeczywistych nie jest w takim przypadku. Model i model Bluma i Smalesa znamy w książce Computable Analysis. I pozornie model w analizie obliczeniowej jest zgodny z modelem klasycznym, ale definicja złożoności obliczeniowej …
1
Zamieszanie na temat pokrycia wierzchołków zliczania redukcji do pokrycia cykli liczenia
To mnie dezorientuje. Jednym z łatwych przypadków liczenia jest sytuacja, gdy problem decyzyjny występuje w i nie ma rozwiązań.PPP Wykład pokazuje, że problem zliczania liczby idealnych dopasowań na grafie dwustronnym (równoważnie, zliczanie liczby okładek cykli na ukierunkowanym wykresie) jest -kompletny.#P#P\#P Dają one redukcję z liczenia okładek wierzchołków o rozmiarze do …
4
Problemy wielomianowe w klasach grafów zdefiniowanych przez zabronione indukowane cykliczne podgrupy
Skrzyżowane z MO . Niech CCC będzie klasą grafu zdefiniowaną przez skończoną liczbę zabronionych indukowanych podrożników, z których wszystkie są cykliczne (zawierają co najmniej jeden cykl). Czy istnieją problemy związane z grafem trudnym dla NP, które można rozwiązać w czasie wielomianowym dla CCC innego niż Clique i Clique? Jeśli dobrze …
3
Czy istnieją niekonstruktywne dowody na istnienie „małych” maszyn Turinga / NFA?
Po przeczytaniu powiązanego pytania dotyczącego niekonstruktywnych dowodów istnienia algorytmów, zastanawiałem się, czy istnieją metody pokazania istnienia „małych” (powiedzmy, stanowych) maszyn obliczeniowych bez ich budowania. Formalnie: załóżmy, że otrzymaliśmy język i naprawiliśmy jakiś model obliczeniowy (NFA / maszyna Turinga itp.).L ⊆ Σ∗L⊆Σ∗L\subseteq \Sigma^* Czy istnieją jakieś niekonstruktywne wyniki istnienia pokazujące, że …
1
Prawie zawsze prawie w porządku
Szukam klasy złożoności, który dotyczy APX jako BPP dotyczy P. Już samo pytanie tutaj , ale być może będzie TCS być bardziej owocne lokalizacja odpowiedzi. Powodem tego pytania jest to, że w praktycznych problemach często trzeba znaleźć przybliżone odpowiedzi (a więc APX) z wystarczająco wysoką pewnością (a więc BPP), co …
1
Model obliczeniowy w SETH
Impagliazzo, Paturi i Calabro, Impagliazzo, Paturi wprowadzili hipotezę czasu wykładniczego (ETH) i hipotezę silnie wykładniczego czasu (SETH). Z grubsza, SETH mówi, że nie ma algorytmu, który rozwiązuje SAT w czasie . 1,99n1,99n1.99^n Zastanawiałem się, co to znaczy złamać SETH. Zdecydowanie musimy znaleźć algorytm, który rozwiązuje SAT w mniej niż krokach, …
2
Intuicja dla klasy UP
Klasa UP jest zdefiniowana jako taka: Klasa problemów decyzyjnych rozwiązanych przez maszynę NP, taką jak Jeśli odpowiedź brzmi „tak”, akceptuje dokładnie jedną ścieżkę obliczeniową. Jeśli odpowiedź brzmi „nie”, wszystkie ścieżki obliczeniowe odrzucają. Próbuję rozwinąć intuicję dla tej definicji. Czy można powiedzieć, że problemy UP są problemami z unikalnymi rozwiązaniami (np. …
2
Czy „Drugi X jest kompletny NP” oznacza, że ​​„X jest kompletny NP”?
Problem „drugiego ” to problem decydowania o istnieniu innego rozwiązania innego niż niektóre dane rozwiązanie problemu.XXX W przypadku niektórych uzupełnieniem druga wersja rozwiązania to zupełne (decydujące o istnieniu innego rozwiązania dla częściowego problemu częściowego uzupełnienia kwadratu łacińskiego), podczas gdy dla innych jest albo trywialne (Drugi NAE SAT), albo nie może …
2
Algorytm czasu liniowego znajdowania przesuniętego maks
Załóżmy, że otrzymujemy tablicę A[1..n]A[1..n]A[1..n] zawierającą nieujemne liczby całkowite (niekoniecznie różne). BBBAAAm=maxi∈[n]B[i]+i.m=maxi∈[n]B[i]+i.m = \max_{i\in [n]} B[i]+i. Oczywistym rozwiązaniem jest sortowanie a następnie obliczanie . Daje to algorytm działający w czasie w najgorszym przypadku.AAAmmmO(nlgn)O(nlg⁡n)O(n \lg n) Czy można to zrobić lepiej? Czy możemy obliczyć czasie liniowym?mmm Moje główne pytanie to powyższe. …
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.