Pytania otagowane jako cc.complexity-theory

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

2
Zależność między stałym parametrem a algorytmem aproksymacyjnym
Stały parametr i przybliżenie to zupełnie inne podejścia do rozwiązywania trudnych problemów. Mają inną motywację. Przybliżenie szuka szybszego wyniku dzięki przybliżonemu rozwiązaniu. Naprawiono parametr szuka dokładnego rozwiązania ze złożonością czasową pod względem wykładniczej lub jakiejś funkcji k i funkcji wielomianowej n, gdzie n jest wielkością wejściową, a k jest parametrem. …
1
Jaka jest złożoność obliczania optymalnych kodów wolnych od prefiksów, gdy częstotliwości są podobne?
Dobrze wiadomo, że istnieje najgorszy przypadek optymalnego algorytmu do obliczania kodu Huffmana w czasie . Poprawiono to na dwa ortogonalne sposoby:θ(nlgn)θ(nlg⁡n)\theta(n\lg n) Optymalne kody wolne od prefiksów można obliczyć szybciej, jeśli zestaw różnych częstotliwości jest mały (np. Rozmiar ): posortuj częstotliwości za pomocą [Munro i Spira, 1976], aby skorzystać z …
5
Twardość problemów FPT
Osłonę wierzchołka można łatwo zredukować do zestawu niezależnego i odwrotnie. Jednak w kontekście sparametryzowanej złożoności zestaw niezależny jest trudniejszy niż osłona wierzchołka. Jądro z wierzchołków istnieje problem pokrycia wierzchołkowego, ale niezależnego zestawu jest biała 1 dysku.2k2k2k Jak zmienia się natura Independent Set w kontekście FPT i dlaczego?
1
Które języki zostały pomyślnie kryptograficznie trapdooredowane?
Obserwacja związana z kryptografią asymetryczną jest taka, że ​​niektóre funkcje są (uważa się) za łatwe do wykonania w jednym kierunku, ale trudne do odwrócenia. Ponadto, jeśli istnieje jakaś informacja „zapadni”, która pozwala na szybkie obliczenie operacji odwrotnej, problem staje się kandydatem do schematu kryptografii klucza publicznego. Klasyczne problemy z zapadniami, …
1
Charaterization Complexity Circuit dla DLogTime i NLogTime
i N L o g T i m e są dwiema najmniejszymi klasami złożoności, jakie mamy. (Należy zauważyć, że w czasie logarytmicznej hierarchia l H jest równe A C 0 i są dwa pierwsze poziom L H ).DLogTimeDLogTime\mathsf{DLogTime}NLogTimeNLogTime\mathsf{NLogTime}LHLH\mathsf{LH}AC0AC0\mathsf{AC}^0LHLH\mathsf{LH} Po zapoznaniu się pytanie , staję się interesuje, czy odstęp pomiędzy tymi …
3
Klasy wykresów z łatwym cyklem hamiltonowskim, ale z TSP NP-twardym
Hamiltona Cykl Problem (HC) polega na znalezieniu cykl, który przechodzi przez wszystkie wierzchołki w danym undirected wykresu. Problem komiwojażera (TSP), polega na znalezieniu się cykl, który przechodzi przez wszystkie wierzchołki w danej krawędzi wykresu ważonych minimalizuje całkowitą odległość, mierzoną przez sumę mas krawędzi w cyklu. HC jest szczególnym przypadkiem TSP …
2
Czy L ma definicję obwodów?
Wiele klas złożoności zdefiniowanych za pomocą maszyn Turinga ma definicje w kategoriach jednorodnych obwodów. Na przykład P można również zdefiniować za pomocą obwodów o jednorodnych rozmiarach wielomianowych, podobnie BPP, NP, BQP itp. Można zdefiniować za pomocą obwodów jednorodnych. Czy istnieje oparta na obwodzie definicja L? Oczywistym pomysłem byłoby dopuszczenie obwodów …
2
Oceniając multilinearyzację obwodu arytmetycznego?
Niech p ( x1, … , Xn)p(x1,…,xn)p(x_1,\ldots,x_n) jest wielomianem wielu zmiennych współczynnikach nad polem faFF . Multilinearization z ppp , oznaczony przez P , jest wynikiem zastąpienia wielokrotnie każdy x d I o d > 1 o x i . Wynikiem jest oczywiście wielomianowy wielomian.p^p^\hat{p}xrejaxidx_i^dre> 1d>1d > 1xjaxix_i Rozważmy następujący …
1
Czy rozmiar członkostwa świadka dla każdego języka NP jest już znany?
Pytanie przyszło mi do głowy, kiedy otrzymałem odpowiedź Dany Moshkovitz na inny temat . Niech będzie językiem NP , a będzie odpowiednią relacją NP . Wiemy, że istnieje pewien wielomian taki, że:LLLRLRLR_Lppp ∀x∈L,,∃w∈0,1p(|x|)(x,w)∈RL∀x∈L,,∃w∈0,1p(|x|)(x,w)∈RL\forall x \in L, \\, \exists w \in \\{0,1\\}^{p(|x|)} \quad (x,w) \in R_L Powyższe stwierdzenie wymaga tylko istnienia …
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.