Pytania otagowane jako cc.complexity-theory

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

2
Testowanie, czy litery można zaplanować, aby uzyskać słowo w zwykłym języku
I ustalić język regularny na alfabetem , i rozważmy następujący problem, który ja nazywam się harmonogram dla . Nieoficjalnie, dane wejściowe dają mi liter i odstępy dla każdej litery (tj. Minimalną i maksymalną pozycję), a moim celem jest umieszczenie każdej litery w tym przedziale, tak aby żadne dwie litery nie …
1
Tardos Funkcja kontrprzykład do Bluma
W tym wątku próba próby Norbet Bluma jest zwięźle obalona przez odnotowanie, że funkcja Tardos jest przeciwne do Twierdzenia 6.P.≠ N.P.P≠NPP \neq NP Twierdzenie 6 : Niech będzie dowolną monotoniczną funkcją boolowską. Załóżmy, że istnieje aproksymator A CNF-DNF, którego można użyć do udowodnienia dolnej granicy C m ( f ) …
2
Najlepsza bieżąca dolna granica dla SAT?
Kontynuując poprzednie pytanie , jakie są najlepsze obecne dolne granice przestrzeni dla SAT? Przez spację dolną rozumiem tutaj liczbę komórek taśmy roboczej używanych przez maszynę Turinga, która używa binarnego alfabetu taśmy roboczej. Stały składnik addytywny jest nieunikniony, ponieważ TM może wykorzystywać stany wewnętrzne do symulacji dowolnej stałej liczby komórek taśmy …
5
Ciekawy o komputerowych dowodach kompletności NP
W artykule „KOMPLEKSOWOŚĆ PROBLEMÓW Z ZADOWOLENIEM” Tomasza J. Schaefera autor wspomniał, że This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the relational complexity could be explored with the help of a computer. The computer would be …
10
Problemy łatwe w przypadku wykresów nieważonych, ale trudne w przypadku wykresów ważonych
Wiele problemów związanych z grafem algorytmicznym można rozwiązać w czasie wielomianowym zarówno na wykresach nieważonych, jak i ważonych. Niektóre przykłady to najkrótsza ścieżka, min. Drzewo rozpinające, najdłuższa ścieżka (w ukierunkowanych grafach acyklicznych), maksymalny przepływ, min. Cięcie, maks. Dopasowanie, optymalne arborescencje, niektóre najgęstsze problemy z podgrafami, maks. Rozłączne nacięcia ukierunkowane, maks. …
3
Uzasadnianie naukowcom asymptotycznej analizy najgorszego przypadku
Pracowałem nad wprowadzeniem niektórych wyników złożoności obliczeniowej do biologii teoretycznej, zwłaszcza ewolucji i ekologii , aby być interesującym / użytecznym dla biologów. Jedną z największych trudności, jakie napotkałem, jest uzasadnienie przydatności asymptotycznej analizy najgorszego przypadku dla dolnych granic. Czy istnieją odniesienia do długości artykułów, które uzasadniają dolne granice i asymptotyczną …
1
Naturalne, niestabilne właściwości wykresu
Podczas testowania właściwości wykresu algorytm wysyła zapytanie do wykresu docelowego o obecność lub brak krawędzi i musi ustalić, czy cel ma określoną właściwość, czy też jest -far od posiadania tej właściwości. (Algorytm może zostać poproszony o powodzenie z błędem 1-stronnym lub 2-stronnym.) Wykres ma -far od posiadania właściwości, jeśli nie …
1
Czym jest twardość UG i czym różni się od twardości NP w oparciu o unikalną hipotezę gier?
Istnieje wiele niedopuszczalności wyników, które opierają się na unikalnym założeniu gier. Na przykład, Zakładając unikalną hipotezę gier, NP jest trudne do przybliżenia maksymalnego problemu cięcia w ramach współczynnika R dla dowolnej stałej R > R GW . (Tutaj R GW = 0,878… jest współczynnikiem przybliżenia algorytmu Goemans – Williamson.) Jednak …
1
Generowanie labiryntu obrony wieży, czyli Znalezienie K najbardziej istotnych węzłów („interwencja nodewise”) na nieważonym wykresie siatkowym
W grze typu tower defense masz siatkę NxM z początkiem, wykończeniem i wieloma ścianami. Wrogowie podążają najkrótszą ścieżką od początku do końca, nie przechodząc przez ściany (zwykle nie są ograniczeni do siatki, ale dla uproszczenia powiedzmy, że są. W obu przypadkach nie mogą poruszać się po przekątnych „otworach”) Problem (przynajmniej …
3
Problemy poza P, które nie są P-trudne
Czytając odpowiedź Petera Shora i wcześniejsze pytanie Adama Crume'a, zdałem sobie sprawę, że mam pewne nieporozumienia na temat tego, co to znaczy być PP\mathsf{P} twardym. Problemem jest PP\mathsf{P} -hard jeśli jakiś problem w PP\mathsf{P} sprowadza się do niego z LL\mathsf{L} (lub jeśli wolisz NCNC\mathsf{NC} ) obniżek. Problem występuje poza PP\mathsf{P} …
4
Artykuły na temat związku między złożonością obliczeniową a geometrią / topologią algebraiczną?
Zastanawiałem się, jakie artykuły powinienem przeczytać, aby zrozumieć to pytanie Nieoczekiwane połączenie z innymi dziedzinami matematyki, takimi jak geometria algebraiczna lub wyższa kohomologia. Być może nawet dziedzina matematyki nie została jeszcze rozwinięta. Być może ktoś opracuje zupełnie nowy kierunek matematyki, aby poradzić sobie z pytaniem P kontra NP. -Od Fortnow …
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.