Pytania otagowane jako cc.complexity-theory

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

2
Powody, by wierzyć
To pytanie zostało przeniesione z Computer Science Stack Exchange, ponieważ można na nie odpowiedzieć na Theoretical Computer Science Stack Exchange. Migrował 6 lat temu . Wydaje się, że wiele osób uważa, że , po części dlatego, że wierzą, że faktoring nie jest możliwy do rozwiązania. (Shiva Kintali wymienił tutaj kilka …
3
Zdecyduj, czy jądro macierzy zawiera jakiś niezerowy wektor, którego wszystkie wpisy to -1, 0 lub 1
Biorąc pod uwagę mmm o nnn binarnego macierzy MMM (wartość wynosi 000 lub 111 ), problemem jest ustalenie, czy istnieje dwoma wektorami binarnymi v1≠v2v1≠v2v_1 \ne v_2 w taki sposób, Mv1=Mv2Mv1=Mv2Mv_1 = Mv_2 (wszystkie operacje wykonywane przez ZZ\mathbb{Z} ). Czy ten problem jest trudny NP? Widać to wyraźnie w NP, ponieważ …
3
Pojęcie monotonicznych obwodów kwantowych
W złożoności obliczeniowej istnieje istotne rozróżnienie między obliczeniami monotonicznymi i ogólnymi, a słynne twierdzenie Razborova stwierdza, że ​​3-SAT, a nawet DOPASOWANIE nie są wielomianowe w monotonicznym modelu obwodów boolowskich. Moje pytanie jest proste: czy istnieje analog kwantowy dla obwodów monotonicznych (lub więcej niż jednego)? Czy istnieje kwantowe twierdzenie Razborowa?
2
Decyzja, czy NC
Chciałbym zapytać o szczególny przypadek pytania „ Decyzja, czy dany obwód NC 0 oblicza permutację ” QiCheng, na który nie udzielono odpowiedzi. Obwód boolowski nazywa się obwodem NC 0 k , jeżeli każda bramka wyjściowa syntaktycznie zależy od co najwyżej k bramek wejściowych. (Mówimy, że bramka wyjściowa g syntaktycznie zależy …
2
Złożoność właściwości topologicznych.
Jestem informatykiem biorącym udział w kursie na temat topologii (posypka topologii punktowej mocno przyprawionej teorią kontinuum). Zainteresowały mnie problemy decyzyjne testujące opis przestrzeni (uproszczeniem) dla właściwości topologicznych; zachowane do homeomorfizmu. Wiadomo na przykład, że określenie rodzaju węzła znajduje się w PSPACE i jest NP-twarde. (Agol 2006; Hass, Lagarias, Pippenger 1999) …
2
Problemy pośrednie NP z efektywnymi rozwiązaniami kwantowymi
Peter Shor pokazał, że dwa z najważniejszych problemów pośrednich NP, faktoring i dyskretny log, są w BQP. Natomiast najbardziej znany algorytm kwantowy dla SAT (poszukiwanie Grovera) zapewnia jedynie kwadratową poprawę w porównaniu z klasycznym algorytmem, co sugeruje, że problemy z całkowitą NP są wciąż trudne do rozwiązania na komputerach kwantowych. …
6
Które problemy z SAT są łatwe?
Jakie są „łatwe regiony” dla satysfakcji? Innymi słowy, wystarczające warunki, aby niektóre solver SAT mógł znaleźć zadowalające zadanie, pod warunkiem, że istnieje. Jednym z przykładów jest sytuacja, w której każda klauzula dzieli zmienne z kilkoma innymi klauzulami, ze względu na konstruktywny dowód LLL, czy są jakieś inne wyniki w tym …
3
Czy istnieje kandydat na naturalny problem w ?
Chcę wiedzieć, czy niejednorodność pomaga w praktyce funkcji obliczeniowych. Łatwo jest pokazać, że istnieją funkcje w , weź dowolną funkcję nieobliczalną i rozważ język { }, który wyraźnie ma proste niejednorodne obwody , ale w ogóle nie da się go obliczyć jednolicie, ale to nie są funkcje, którymi się interesuję.P/poly−PP/poly−PP/poly …
6
Jak określa się liczby rzeczywiste w obliczeniach?
To może być podstawowe pytanie, ale czytałem i próbowałem zrozumieć artykuły na takie tematy, jak obliczenia równowagi Nasha i liniowe testy degeneracji, i nie byłem pewien, jak liczby rzeczywiste są określone jako dane wejściowe. Na przykład, kiedy stwierdzono, że LDT ma pewne dolne granice wielomianu, w jaki sposób określa się …
2
Jakie są konsekwencje parzystości-L = P?
Parzystość-L jest zestawem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może jedynie rozróżniać między liczbą parzystą lub nieparzystą liczbą ścieżek „akceptacji” (zamiast zerowej lub niezerowej liczby ścieżek akceptacji), i która jest dodatkowo ograniczone do pracy w przestrzeni logarytmicznej. Rozwiązanie liniowego układu równań powyżej ℤ 2 jest kompletnym problemem dla parzystości-L, …
1
Złożoność zasilania macierzy
Niech będzie kwadratową macierzą liczb całkowitych, a niech n będzie liczbą całkowitą dodatnią. Interesuje mnie złożoność następującego problemu decyzyjnego:MMMnnn Czy prawy górny wpis dodatni?MnMnM^n Zauważ, że oczywiste podejście iterowanego kwadratu (lub innego jawnego obliczenia) wymaga od nas potencjalnie obsługi liczb całkowitych o podwójnie wykładniczej wielkości, tj. Mających wykładniczo wiele bitów. …
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.