Dostęp do wyroczni zapewniłby duże, super-wielomianowe przyspieszenie wszystkiego w N P - P (zakładając, że zestaw nie jest pusty). Nie jest jednak jasne, ile P skorzystałby z tego dostępu do wyroczni. Oczywiście przyspieszenie w P nie może być wielomianowe, ale nadal może być wielomianowe. Na...
To pytanie zostało przeniesione z Computer Science Stack Exchange, ponieważ można na nie odpowiedzieć na Theoretical Computer Science Stack Exchange. Migrował 3 lata temu . W artykule naukowym z 2016 r. „ Realizacja skalowalnego algorytmu Shora ” [ 1 ] autorzy
Problem nie wszystkie równe SAT (NAE -SAT), biorąc pod uwagę zbiór klauzul nad zestawem zmiennych boolowskich, tak że każda klauzula zawiera co najwyżej literałów, pyta, czy istnieje przyporządkowanie zmiennych do takich wartości, że każda klauzula zawiera co najmniej jeden prawdziwy i co najmniej...
Obecnie próbuję znaleźć problemy pełne EXPSPACE (głównie w celu znalezienia inspiracji do redukcji) i jestem zaskoczony małą liczbą nadchodzących wyników. Jak dotąd je znalazłem i mam problem z rozwinięciem listy: uniwersalność (lub inne właściwości) wyrażeń regularnych z potęgowaniem. problemy...
Minęło ponad rok od wycofania i korekty w styczniu 2017 r. Czy są jakieś wiadomości? Jeśli nie, czy to normalne, że walidacja trwa tak długo? Spodziewałbym się, że zyska dużo uwagi. Czy ktoś z ważnych osób wypowiedział się, by poprzeć / wątpić w quasi-wielomianowy...
Wielomian f ( x 1 , … , x n )f(x1,…,xn)f(x_1,\ldots,x_n) jest rzutem monotonicznym wielomianu g ( y 1 , … , y m ),g(y1,…,ym)g(y_1,\ldots,y_m) jeśli = poli , i istnieje przypisanie takie, że . Oznacza to, że możliwe jest zastąpienie każdej zmiennej o o zmiennej lub stałą lubm ( n ) π : { y 1 , … ,...
Niektórzy z was mogli śledzić to pytanie , które zostało zamknięte z powodu braku poziomu badań. Wyciągam więc część pytania, która jest na poziomie badawczym. Oprócz „prostszych” technik, takich jak redukcja do sortowania lub problem z WYŁĄCZENIEM, jakie techniki zostały zastosowane, aby...
Obecnie bitcoin ma system proof of work (PoW) wykorzystujący SHA256. Inne funkcje skrótu wykorzystują wykresy wykorzystania systemu dowodu pracy, częściowe odwrócenie funkcji skrótu. Czy można zastosować problem decyzyjny w teorii węzłów, taki jak rozpoznawanie węzłów, i uczynić z niego funkcję...
Widoczna jest redukcja z CLIQUE na k-Color, ponieważ oba są NP-Complete. W rzeczywistości mogę go zbudować, tworząc redukcję z CLIQUE do 3-SAT z redukcją z 3-SAT do k-Color. Zastanawiam się, czy istnieje rozsądna bezpośrednia redukcja między tymi problemami. Powiedzmy, redukcję, którą mógłbym...
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...
Oryginalne twierdzenie o niedeterministycznej hierarchii czasu wynika z Cooka (link do S. Cooka, Hierarchia niedeterministycznej złożoności czasu , JCSS 7 343–353, 1973). Twierdzenie to stwierdza, że dla dowolnych liczb rzeczywistych i , jeśli wówczas NTIME ( ) jest ściśle zawarty w NTIME ( ).r 2...
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....
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...
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...
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.)...
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...
To pytanie stanowi odpowiedź na pytanie o algorytmy DNA zadane przez Aaditę Mehrę . W komentarzach Joe Fitzsimmons powiedział częściowo: Promień układu musi być skalowany proporcjonalnie do masy, aby tego uniknąć. Moc obliczeniowa jest skalowana co najwyżej liniowo w masie. Zatem twoja...
W złożoności obliczeniowej optyki liniowej ( ECCC TR10-170 ) Scott Aaronson i Alex Arkhipov twierdzą, że jeśli komputery kwantowe mogą być skutecznie symulowane przez klasyczne komputery, hierarchia wielomianowa upadnie na trzeci poziom. Problemem motywującym jest próbkowanie z rozkładu określonego...
Aby sprawdzić moje zrozumienie, chciałbym podzielić się przemyśleniami na temat wymagań energetycznych obliczeń. Jest to kontynuacja mojego poprzedniego pytania i może być związana z pytaniem Vinaya dotyczącym praw ochrony . Przyszło mi do głowy, że z termodynamicznego punktu widzenia prowadzenie...
Czytałem „ Czy P w porównaniu z NP jest formalnie niezależny? ”, Ale mnie to zaskoczyło. Uważa się, że w teorii złożoności . Moje pytanie dotyczy tego, co jeśli nie da się tego udowodnić (powiedzmy w Z F C ). (Załóżmy, że dowiadujemy się tylko, że P ≠ N P jest niezależny od Z F C, ale nie ma...