Pytania otagowane jako cc.complexity-theory

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

3
Ograniczenia przetwarzania równoległego
Jestem ciekawy w szerokim znaczeniu tego, co wiadomo na temat algorytmów równoległych w P. Znalazłem następujący artykuł w Wikipedii na ten temat: http://en.wikipedia.org/wiki/NC_%28complexity%29 Artykuł zawiera następujące zdanie: Nie wiadomo, czy NC = P, ale większość badaczy podejrzewa, że ​​jest to fałsz, co oznacza, że ​​prawdopodobnie istnieją pewne możliwe do rozwiązania …
4
Algorytmy DNA i kompletność NP
Jaki jest związek między algorytmami DNA a klasami złożoności określonymi za pomocą maszyn Turinga? Czym są pomiary złożoności, takie jak czas i przestrzeń w algorytmach DNA? Czy można je wykorzystać do rozwiązania problemów związanych z NP-zupełnymi, takich jak TSP, których maszyny von Neumann nie są w stanie rozwiązać w praktyce?
6
Referencje na temat dolnych granic obwodu
Preambuła Interaktywne systemy dowodowe i protokoły Arthura-Merlina zostały wprowadzone przez Goldwassera, Micali i Rackoffa i Babai w 1985 roku. Początkowo sądzono, że ten pierwszy jest potężniejszy od drugiego, ale Goldwasser i Sipser wykazali, że mają taką samą moc ( w odniesieniu do rozpoznawania języka). Dlatego w tym poście użyję tych …
2
Dolne granice dla formuł o stałej głębokości?
Wiemy dużo o ograniczeniach obwodów o stałej głębokości (rozmiar wielomianowy). Ponieważ formuły o stałej głębokości (rozmiar wielomianowy) są jeszcze bardziej ograniczonym modelem obliczeń, wszystkie problemy, o których wiadomo, że nie występują w AC 0, również nie są obliczalne na podstawie wzoru o stałej głębokości. Ponieważ jednak jest to łatwiejszy model, …
6
Jaki jest najlepszy sposób na uzyskanie rzutu monetą zbliżoną do uczciwej z identycznych monet tendencyjnych?
(Von Neumann podał algorytm, który symuluje uczciwą monetę, mając dostęp do identycznych monet o tendencyjnym charakterze. Algorytm ten potencjalnie wymaga nieskończonej liczby monet (choć w oczekiwaniu wystarcza ostatecznie ich wiele). Pytanie dotyczy przypadku, gdy dozwolona liczba rzutów monetą jest zobowiązany.) Załóżmy, że mamy nnn identycznych monet o nastawieniu δ=P[Head]−P[Tail]δ=P[Head]−P[Tail]\delta=P[Head]-P[Tail] . …
4
Które wyniki teorii złożoności istotnie wykorzystują jednolitość?
Dowód separacji klas złożoności używa jednorodności klas złożoności zasadniczo, jeśli dowód nie dowodzi wyniku dla wersji niejednorodnej, na przykład dowody oparte na przekątnej (takie jak twierdzenia dotyczące hierarchii czasu i przestrzeni) w istotny sposób wykorzystują jednolitość, ponieważ muszą symulować programy w mniejsza klasa. Które wyniki teorii złożoności (inne niż dowody …
3
Wykorzystanie złożoności Kołmogorowa jako wejściowego „rozmiaru”
SSSI(n)={w∈S:|w|=n}I(n)={w∈S:|w|=n}I(n) = \{w \in S : |w| = n\}nnnT(w)T(w)T(w)AAAwwwAAAfn=maxw∈I(n)T(w).fn=maxw∈I(n)T(w). f_n = \max_{w \in I(n)} T(w). Zdefiniujmy teraz zbiory wszystkich danych wejściowych o złożoności Kołmogorowa , i zdefiniujmy sekwencję Tutaj jest średnią sekwencją czasu pracy dla , z wyjątkiem przypadków, gdy „rozmiar” danych wejściowych jest złożonością Kołmogorowa, a nie ich długością.n …
6
Czy istnieje naturalny problem w czasie quasi-wielomianowym, ale nie w czasie wielomianowym?
László Babai niedawno udowodnił, że problem z izomorfizmem grafowym występuje w quasipolomomialnym czasie . Zobacz także jego przemówienie na Uniwersytecie w Chicago, notatkę z przemówień Jeremy Kun GLL post 1 , GLL post 2 , GLL post 3 . Zgodnie z twierdzeniem LADNER, o ile P.≠NP.P≠N.P.P \neq NP , a …
2
Czy każde wyzwanie obliczeniowe można przekształcić w proof-of-work?
Pozornie bezcelowość wydobywania kryptowalut wywołała pytanie o przydatne alternatywy, zobacz te pytania na Bitcoin , CST , MO . Zastanawiam się, czy istnieje algorytm, który może przekonwertować praktycznie każde wyzwanie obliczeniowe doC\mathcal C (którego rozwiązanie można skutecznie zweryfikować) na inne takie wyzwanie Ψ ( C)Ψ(C)\Psi(\mathcal C) (które jest używane do …
2
Jak szybko niedeterministyczny algorytm dla problemu pełnego EXPTIME musiałby sugerować
Jak szybko niedeterministyczny algorytm dla problemu pełnego EXPTIME musiałby sugerować ? Algorytm niedeterministyczny czasu wielomianowego natychmiast implikowałby to, ponieważ ale nikt nie wierzy, że . Jeśli zrobiłem algebrę w prawo (patrz poniżej), twierdzenie o hierarchii czasu nadal dawałoby implikację dla czasów uruchamiania dla dowolnego wielobiegunowego , ale dla wszystko, co …
3
Ile czasu rozpoznaje palindromy w przestrzeni logarytmicznej?
Dobrze wiadomo, że palindromy można rozpoznać w czasie liniowym na maszynach Turinga z taśmami, ale nie na maszynach Turinga z pojedynczą taśmą (w takim przypadku potrzebny czas jest kwadratowy). Algorytm czasu liniowego wykorzystuje kopię danych wejściowych, a zatem wykorzystuje również przestrzeń liniową.222 Czy potrafimy rozpoznać palindromy w czasie liniowym wielowarstwowej …
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.