Pytania otagowane jako cc.complexity-theory

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

1
Nauka z (podpisanymi) błędami
Background––––––––––––––Background_\underline{\bf Background} W 2005 r. Regev [1] wprowadził problem uczenia się z błędami (LWE), uogólnienie problemu parzystości uczenia się z błędem. Założenie o twardości tego problemu dla niektórych wyborów parametrów leży obecnie u podstaw dowodów bezpieczeństwa dla wielu kryptosystemów post kwantowych w dziedzinie kryptografii opartej na sieci. „Kanoniczne” wersje LWE …
1
Sparametryzowana złożoność liczenia rowerów
W poprzednim pytaniu Sparametryzowany algorytm znajdowania biklików zapytałem, czy istnieją szybkie sparametryzowane algorytmy do znalezieniak×kk×kk\times k-biclique in an nnn wykres wierzchołków i dowiedziałem się, że był otwarty, jeśli jest FPT wrt kkk. To samo odnosi się do liczeniak×kk×kk\times k-bikiety, czy wiadomo, że to #W\[1\]W\[1\]W\[1\]-hard wrt kkk (lub jakieś inne pojęcie …
1
„Właściwy” warunek jednolitości dla klasy Nicka
DLOGTIME jest zdefiniowany na stronie http://en.wikipedia.org/wiki/DLOGTIME nazwa jest zdefiniowany na stronie http://en.wikipedia.org/wiki/L_%28complexity%29 nazwa i nazwa są zdefiniowane na stronie http://en.wikipedia.org/wiki/NC_%28complexity%29 LL\operatorname{L} NCNC\operatorname{NC}NCnNCn\operatorname{NC}^n DLOGTIME wydaje się być najmniejszym, który może działać. Czytałem w różnych miejscach, , chociaż każde miejsce, w jakim okazało się, że wyniki, które stwierdza warunek jednorodności używa - …
1
Czy Max-Cut APX-complete na grafach bez trójkątów?
W problemie Max-Cut szuka się podzbioru S wierzchołków danego prostego niekierowanego wykresu, tak że liczba krawędzi między S a dopełnieniem S jest tak duża, jak to możliwe. Max-Cut jest kompletny APX na wykresach ograniczonego stopnia [PY91], i faktycznie APX-kompletny na wykresach sześciennych (tj. Grafach stopnia 3) [AK00]. Max-Cut jest NP-kompletny …
2
Czy mogę ograniczyć liczebność zbioru, jeśli wiadomo, że testowanie członkostwa w nim jest zakończone NP?
Chciałbym ograniczyć się do liczności zbioru grafów dysków jednostkowych N.NNwierzchołki. Wiadomo, że sprawdzenie, czy wykres należy do tego zestawu, jest trudne dla NP. Czy prowadzi to do jakiejkolwiek dolnej granicy liczności, zakładając, że P≠≠\neq NP? Załóżmy na przykład, że na wszystkich wykresach występuje kolejność N.NNwierzchołki. Czy twardość NP oznaczałaby wówczas, …
1
Stała macierzy i z wyznaczników
Niech będzie macierzą lub z wpisami . Czy ktoś może mi dostarczyć macierz , aby ? Jaki jest najmniejszy znany jawny B , taki że \ operatorname {per} (A) = \ det (B) ? Wszelkie odniesienia do tego z wyraźnymi przykładami?AZAA3×33)×3)3 \times 34×44×44 \times 4aijzajajota_{ij}BbBper(A)=det(B)za⁡(ZA)=det(b)\operatorname{per}(A) = \det(B)BbBper(A)=det(B)za⁡(ZA)=det(b)\operatorname{per}(A) = \det(B) Niektóre …
1
Literatura wokół NP vs EXPTIME
Nawet jeśli nie jest to kluczowa kwestia, nie widzę żadnej literatury wokół tego pytania. Czy są wyniki relatywizacji? Czy nie byłoby łatwo udowodnić ścisłe włączenie poprzez dostosowanie niedeterministycznego twierdzenia o hierarchii czasu poprzez badanie wszystkich możliwych ścieżek maszyny NP?
1
Języki zapytań do baz danych dla wydajnych zapytań
Wydaje się, że w popularnych językach zapytań dotyczących relacyjnych baz danych możliwe jest tworzenie zapytań, które będą wymagały dużej ilości zasobów. W praktyce administratorzy baz danych zarządzają tym, ograniczając ilość pamięci na zapytanie i sprawdzając, czy w bazie danych nie ma żadnych długotrwałych zapytań. Wydaje się to raczej ad-hoc, czy …
1
Analiza wygładzona: jeśli problem ma złożoność pseudopolinomialną, czy jest on płynny?
Zafascynowała mnie niezwykła eksplozja w analizie wygładzonej i uderzyło mnie stwierdzenie w artykule Analiza wygładzonego programowania liczb całkowitych . Stwierdzono, że programowanie liniowe w liczbach całkowitych jest wygładzone P, jeśli jest ograniczone wielomianowo. Było to niezbędne, ponieważ programowanie liczb całkowitych jest pseudo-wielomianowe! Pytanie zatem brzmi: Czy to uniwersalnie przenosi się …
1
Niejednolici kontra Jednolici Przeciwnicy
To pytanie powstało w kontekście kryptografii, ale poniżej przedstawię je w kategoriach teorii złożoności, ponieważ ludzie tutaj są bardziej zaznajomieni z tym ostatnim. To pytanie dotyczy problemów w NP, ale nie w średniej P / poli i pokonania premii przez Oracle Access . Nieformalne oświadczenie: kiedy nierównomiernym przeciwnikom (tj. Wielorakiej …
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.