Pytania otagowane jako cc.complexity-theory

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

2
Klasa złożoności odpowiadająca sortowaniu
Dwie części TCS to algorytmy i złożoność. Upraszczając powiem, że algorytmy to badanie górnych granic, pokazujące, że możesz coś zrobić (przy danych ograniczonych zasobach), a złożoność polega na pokazaniu, że nie możesz tego zrobić bez minimalnych zasobów. Tak często problem algorytmiczny pojawia się w modelu decyzyjnym, aby umieścić go w …
2
Kompromis czasoprzestrzenny i najlepszy algorytm
Rozważmy język taki jak:LLL L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L \in DTIME(O(f(n))) \cap DSPACE(O(g(n))) i tak L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n))) Innymi słowy, najszybsza maszyna oblicza L w czasie O ( f ( n ) ), a najbardziej wydajna pod względem przestrzeni maszyna M ' oblicza L , używając przestrzeni O ( g ( n …
4
Zliczanie liczby osłon wierzchołków: kiedy jest to trudne?
Rozważmy problem # P-zupełny liczenia liczby osłon wierzchołków danego wykresu G=(V,E)G=(V,E)G = (V, E) . Chciałbym wiedzieć, czy jest jakikolwiek wynik pokazujący, jak twardość takiego problemu zmienia się w zależności od parametru (na przykład ).GGGd=|E||V|d=|E||V|d = \frac{|E|}{|V|} Mam wrażenie, że problem powinien być łatwiejszy zarówno wtedy, gdy jest rzadki, jak …
3
Złożoność sprawdzania, czy dwa CNF mają taką samą liczbę rozwiązań
Biorąc pod uwagę dwa CNF, jeśli mają taką samą liczbę zadań, aby były prawdziwe, odpowiedz „Tak”, w przeciwnym razie odpowiedz „Nie”. Łatwo zauważyć, że jest to w , ponieważ jeśli znamy dokładną liczbę rozwiązań dla tych dwóch CNF, po prostu je kampanujemy i odpowiadamy „Tak” lub „Nie”.P#PP#PP^{\#P} Jaka jest złożoność …
1
Wykrywanie relacji liczb całkowitych dla podzbioru sumy lub NPP?
Czy istnieje sposób na zakodowanie wystąpienia Sumy Podzbioru lub Problemu Podziału Liczby, aby (małe) rozwiązanie relacji liczb całkowitych dało odpowiedź? Jeśli nie zdecydowanie, to w pewnym sensie probabilistycznym? Wiem, że LLL (i być może PSLQ) zostały zastosowane z umiarkowanym sukcesem w rozwiązywaniu problemów sumy częściowej w regionie „niskiej gęstości”, w …
3
Jak trudno jest zredukować terminację do częściowej poprawności?
Jeśli jesteś zaznajomiony z weryfikacją programu, prawdopodobnie wolisz przeczytać pytanie przed tłem . Jeśli nie jesteś zaznajomiony z weryfikacją programu, być może nadal będziesz w stanie odpowiedzieć na to pytanie, ale prawdopodobnie wolisz najpierw przeczytać tło . tło Często mówi się, że sprawdzenie częściowej poprawności jest nierozstrzygalne. Dla celów dyskusji …
5
Czy redukcje powinny nas bardziej lub mniej optymistycznie podchodzić do rozwiązania problemu?
Wydaje mi się, że większość teoretyków złożoności ogólnie uważa następującą zasadę filozoficzną: Jeśli nie możemy wymyślić skuteczny algorytm dla problemu i możemy zmniejszyć problemu A do problemu B , wtedy prawdopodobnie nie jest skuteczny algorytm dla problemu B , albo.ZAAAZAAAbBBbBB Dlatego, na przykład, gdy nowy problem zostanie udowodnione, NP-complete po …
1
obwodu
Czy wiadomo, czy problem z oceną obwodu występuje w ? Co powiesz na (uniform )? N C 1 A L O g T i m e N C 1NC1NC1\mathsf{NC^1}NC1NC1\mathsf{NC^1}ALogTimeALogTime\mathsf{ALogTime}NC1NC1\mathsf{NC^1} Wiemy, że obwody o głębokości można oceniać za pomocą obwodów o głębokości gdzie jest stałą uniwersalną. Oznacza to, że obwody o …
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.