Pytania otagowane jako cc.complexity-theory

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

1
Jaka jest klasyfikacja złożoności teorii portfela w ekonomii finansowej?
Jak wszyscy wiecie, kryzys finansowy z 2008 r. Ciągle wypada. Zastanawiałem się, jak teoria złożoności pasuje do tego wszystkiego, kiedy zdałem sobie sprawę, że nie znam podstawowych klas złożoności związanych z ekonomią finansową. Więc moje pytanie brzmi: jaka jest klasyfikacja złożoności (jeśli w ogóle) w teorii portfela Markowitza w ogóle, …
1
Dolne granice funkcji progowej
W złożoności drzewa decyzyjnego funkcji boolowskiej bardzo dobrze znaną metodą dolnej granicy jest znalezienie (przybliżonego) wielomianu reprezentującego funkcję. Paturi podał charakterystykę symetrycznych funkcji boolowskich (częściowych i całkowitych) pod względem oznaczonej ilościΓΓ\Gamma: Twierdzenie ( Paturi ): Niechfff być dowolną niestałą funkcją symetryczną i oznaczać fk=f(x)fk=f(x)f_k=f(x) kiedy |x|=k|x|=k|x|=k (tj. masa młota wynosząca …
3
Interaktywne dowody za pomocą Postselection?
Zdefiniuj model obliczeniowy MPostBQP, aby był identyczny z PostBQP, z wyjątkiem tego, że dopuszczamy wielomianowo wiele pomiarów kubitowych przed pomiarem selekcyjnym i pomiarem końcowym. Czy możemy podać jakiekolwiek dowody wskazujące, że MPostBQP ma większą moc niż PostBQP? Zdefiniuj MPostBQP [k], aby umożliwić wiele rund pomiaru i wyboru po dokonaniu ostatecznego …
1
Twardość NP specjalnego przypadku problemu upakowania ortogonalnego
Pozwolić VVV być zestawem DDD-wymiarowe kształty prostokątne. Dlad∈{1,...,D}d∈{1,...,D}d \in \{1,...,D\} i v∈Vv∈Vv \in V, wd(v)∈Q+wd(v)∈Q+w_d(v) \in \mathbb{Q}^{+} opisuje długość vvv w wymiarze ddd. Ta sama notacja jest używana dla konteneraCCC. TheDDD-wymiarowy problem pakowania ortogonalnego (OPP-DDD) ma zdecydować, czy VVV pasuje do pojemnika CCCbez nakładania się. Formalnie rzecz biorąc, problemem jest …
1
Czy problem tworzenia kopii zapasowej NP jest kompletny?
Czy następujący problem decyzyjny NP-zupełny: Niech będzie nieukierowanym wykresem i dwiema liczbami całkowitymi. Czy można wybrać dla każdego wierzchołka dokładnie różnych sąsiadów, tak że żaden węzeł nie zostanie wybrany więcej niż razy.GGGb≤cb≤cb \le cGGGbbbccc Przypadek można rozwiązać dla dowolnego czasie wielomianowym, stosując maksymalne dopasowanie.b=1b=1b = 1ccc Motywacja: każdy węzeł chce …
1
Czy istnieje związek między teorią złożoności obliczeniowej a teorią systemów złożonych?
Teoria złożoności obliczeniowej klasyfikuje problemy według ich nieodłącznej trudności. Teoria złożonych systemów dotyczy systemów, które wykazują zachowania, które oczywiście nie wynikają z właściwości poszczególnych części systemu. Przykłady obejmują systemy chaotyczne, złożone systemy adaptacyjne lub systemy nieliniowe. Czy istnieje formalny pomost między tymi polami? Co do tego, co jest warte, koncepcja …
1
Rzeczywista złożoność bitowa mnożenia macierzy wynosi
Mnożenie macierzy przy użyciu techniki regularnej (iloczyn wewnętrzny rzędów i kolumn) O (n3))O(n3))O(n^{3}) mnożenia i O (n3))O(n3))O(n^{3})wzbogacenie. Jednak przy założeniu, że wpisy o jednakowej wielkości (liczba bitów w każdym wpisie obu macierzy jest mnożona) o wielkościmmm bitów, operacja dodawania faktycznie się dzieje O (n3)n m ) = O (n4m )O(n3)nm)=O(n4m)O(n^{3}nm) …
1
właściwości zamknięcia IP (2pfa) i AM (2pfa)
IP (2pfa) i AM (2pfa) to klasy języków rozpoznawane z błędem granicznym odpowiednio w prywatnych i publicznych wersjach monet, interaktywnych systemów dowodzenia z weryfikatorami, które są probabilistycznymi automatami skończonymi z dwukierunkową głowicą wejściową. Czy znane są jakieś właściwości zamknięcia tych klas?
5
Wyniki pokazujące istnienie / nieistnienie grafów skończonych o określonych właściwościach obliczeniowych implikują pewne wyniki złożoności
Czy są jakieś znane wyniki wskazujące, że istnienie (lub nieistnienie) grafów skończonych o określonych właściwościach obliczeniowych implikuje pewne wyniki złożoności (takie jak P = NP)? Oto jeden całkowicie hipotetyczny wynik: jeśli istnieje skończony wykres z rozłożonymi krawędziami A, B, C i D, tak że wszystkie maksymalne dopasowania albo zawierają wszystkie …
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.