Pytania otagowane jako cc.complexity-theory

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

13
Łatwy problem decyzyjny, trudny problem wyszukiwania
Decyzja, czy istnieje równowaga Nasha, jest łatwa (zawsze tak jest); jednak znalezienie takiego uważa się za trudne (jest to PPAD-Complete). Jakie są inne przykłady problemów, w których wersja decyzyjna jest łatwa, ale wersja wyszukiwania jest stosunkowo trudna (w porównaniu z wersją decyzyjną)? Byłbym szczególnie zainteresowany problemami, w których wersja decyzyjna …
1
NP-Kompletność problemu decyzyjnego dla uogólnionego 15-puzzle
Interesuje mnie naturalne uogólnienie słynnej 15-puzzli , w których musisz przesuwać bloki, dopóki nie posortujesz wszystkich podanych liczb (zwykle jest przerwa 1 blok). Teraz uogólnieniem byłoby zwiększenie rozmiaru układanki z 15 do , gdzie jedno pole jest wolne. Stworzyłem małą ilustrację (przerywane strzałki pokazują dozwolone ruchy, a dolna konfiguracja pokazuje …
7
Formalne pojęcie złożoności energetycznej problemów obliczeniowych
Złożoność obliczeniowa obejmuje badanie złożoności problemów obliczeniowych w czasie lub przestrzeni. Z punktu widzenia przetwarzania mobilnego energia jest bardzo cennym zasobem obliczeniowym. Czy istnieje dobrze zbadana adaptacja maszyn Turinga, które odpowiadają za energię zużywaną podczas wykonywania algorytmów. Czy istnieją ustalone klasy złożoności energetycznej dla problemów obliczeniowych? Referencje są mile widziane.
2
Jeśli P = NP, czy moglibyśmy uzyskać dowody hipotezy Goldbacha itp.?
To naiwne pytanie z mojej wiedzy; z góry przeprasza. Hipoteza Goldbacha i wiele innych nierozwiązanych pytań w matematyce można zapisać jako krótkie formuły w rachunku predykatów. Na przykład artykuł Cooka „Czy komputery mogą rutynowo odkrywać dowody matematyczne?” formułuje tę hipotezę jako ∀ n [ ( n > 2 ∧ 2 …
5
Mnożenie liczb całkowitych, gdy jedna liczba całkowita jest ustalona
Niech AAA będzie stałą dodatnią liczbą całkowitą o rozmiarze nnn bitów. Można odpowiednio wstępnie przetworzyć tę liczbę całkowitą. Biorąc pod uwagę kolejną dodatnią liczbę całkowitą BBB o rozmiarze mmm bitów, jaka jest złożoność mnożenia ABABAB ? ϵ = 0(max(n,m))1+ϵ(max(n,m))1+ϵ(\max(n,m))^{1+\epsilon}ϵ=0ϵ=0\epsilon=0
2
Klasy złożoności semantycznej a składniowej
W swojej książce „Computational Complexity” Papadimitriou pisze: RP jest w pewnym sensie nową i niezwykłą klasą złożoności. Żadna żadna wieloznacznie niedeterministyczna maszyna Turinga nie może być podstawą do zdefiniowania języka w RP. Aby maszyna N mogła zdefiniować język w RP , musi mieć niezwykłą właściwość, która na wszystkich wejściach albo …
3
Konsekwencje NC = P?
Zoo złożoności wskazuje we wpisie na EXP, że jeśli L = P, to PSPACE = EXP. Ponieważ NPSPACE = PSPACE autorstwa Savitcha, o ile mogę powiedzieć, podstawowy argument dopełniania rozszerza się, aby pokazać, że Wiemy również, że L NL NC \ subseteq P poprzez zmienną hierarchię ograniczoną zasobami Ruzzo.(NL=P)⇒(PSPACE=EXP).(NL=P)⇒(PSPACE=EXP).(\text{NL} = …
17
Twardość przeskakuje w złożoności obliczeniowej?
Problem z minimalną przepustowością polega na znalezieniu kolejności węzłów wykresu na linii całkowitej, która minimalizuje największą odległość między dowolnymi dwoma sąsiadującymi węzłami. -caterpillar jest drzewem, utworzony z głównego toru hodując ścieżki krawędziach rozłączny o długości co najwyżej z węzłami ( nazywa długości włosów). Problem minimalnej przepustowości występuje w dla 2-gąsiennic, …
3
Najtrudniejszy znany problem naturalny w P?
Zastanawiam się, jaka jest (obecnie) największa liczba , tak że znany jest naturalny problem z następującymi właściwościami:kkk algorytm został już, że do tego problemu.O(nk)O(nk)O(n^k) Dla każdego ustalonego algorytmu no znany jest ten sam problem. (Zauważ, że istnieć szybszy algorytm , tylko nie jest jeszcze znany, więc nie szukam sprawdzonej dolnej …
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.