Pytania otagowane jako reference-request

Prośba o referencję jest wykorzystywana, gdy autor musi wiedzieć o pracy związanej z pytaniem.

1
Deterministyczna redukcja błędów, najnowocześniejszy?
Załóżmy, że jeden ma losowy (BPP) algorytm ZAAA przy użyciu rrr bitów przypadkowości. Istnieją naturalne sposoby na zwiększenie prawdopodobieństwa sukcesu do 1 - δ1−δ1-\delta dla każdego wybranego δ> 0δ>0\delta>0 Niezależne przebiegi + większość głosów: przebieg ZAAA niezależnie T.= Θ ( log( 1 / δ)T=Θ(log⁡(1/δ)T=\Theta(\log(1/\delta) razy ) i przyjmowanie większości głosów …
1
Entropia i złożoność obliczeniowa
Są badacze wykazujący, że bit wymazywania musi zużywać energię, czy teraz są jakieś badania dotyczące średniego zużycia energii algorytmu o złożoności obliczeniowej ? Wydaje mi się, że złożoność obliczeniowa F ( n ) jest skorelowana ze średnim zużyciem energii, mam nadzieję, że mogę tu znaleźć odpowiedź.F(n)F(n)F(n)F(n)F(n)F(n)
1
Pierwotne źródło równoważności niedeterministycznej weryfikacji wielomianu i deterministycznej weryfikacji czasu wielomianu
Kto jako pierwszy pokazał, że dany język jest w NP, jeśli certyfikat dla tego języka można zweryfikować w czasie wielomianowym? Czy mamy dokument, który formalnie to potwierdza? Kiedy społeczność TCS zaczęła kłaść nacisk na niedeterminizm na rzecz weryfikowalności? Nie mogę znaleźć dla tego dobrego odniesienia poza tekstami takimi jak Papadimitriou, …
2
Jaka jest najgorsza złożoność sita z polem liczbowym?
Biorąc kompozytu Pole numeru sita ogólnie najlepiej znane algorytm faktoryzacji całkowitymi faktoryzacji N . Jest to algorytm randomizowany i otrzymujemy oczekiwaną złożoność O ( e √N∈NN∈NN\in\Bbb NNNNdo współczynnikaN.O(e649√(logN)13(loglogN)23)O(e649(log⁡N)13(log⁡log⁡N)23)O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)NNN Szukałem informacji o złożoności najgorszych przypadków w tym randomizowanym algorytmie. Nie mogę jednak znaleźć informacji. (1) Jaka jest …
5
Aplikacje kombinatoryki addytywnej w projektowaniu algorytmów
Czytam ankiety Trevisana i Lovetta dotyczące zastosowań dodatku kombinatorycznego w TCS. Większość tych aplikacji ma złożoność obliczeniową , np. Niższe granice. Zastanawiam się, czy kombinatoryka addytywna znalazła również zastosowania w projektowaniu algorytmów . Motywacja mojego pytania jest następująca: chociaż związek między kombinatoryką addytywną a złożonością wydaje się dość naturalny, jestem …
1
Optymalne losowe sortowanie porównania
Więc wszyscy znamy dolną granicę drzewa na podstawie najgorszego przypadku porównań wykonanych przez (deterministyczny) algorytm sortowania porównań. Nie dotyczy losowego sortowania porównań (jeśli mierzymy oczekiwane porównania dla danych wejściowych w najgorszym przypadku). Na przykład, dla , dolna granica deterministyczna wynosi pięć porównań, ale algorytm randomizowany (losowo permutuje dane wejściowe, a …
2
Poszukuję źródła literatury do naśladowania
Jestem pewien, że nie jako pierwszy rozważyłem pomysł, który zamierzam przedstawić. Przydałoby się jednak znalezienie literatury związanej z tym pomysłem. Chodzi o to, aby zbudować Maszynę Turinga M z właściwością, że jeśli P = NP, wówczas M rozwiąże 3-SAT w czasie wielomianowym. (Wybór 3-SAT jest arbitralny. To może być naprawdę …
2
Cykl hamiltonowski na wykresach bez małych cykli
Odpowiadając na to pytanie w cstheory , (nieformalnie) udowodniłem w locie następujące twierdzenie: Twierdzenie : Dla dowolnego ustalonego sonda cyklu Hamiltoniana pozostaje NP-kompletna, nawet jeśli jest ograniczona do płaskich dwustronnych grafów niekierowanych o maksymalnym stopniu 3, które nie zawierają cykli o długości ≤ l .l≥3l≥3l \geq 3≤l≤l\leq l Wydaje się …
1
Twardość APX oznacza brak QPTAS?
Szybkie wyszukiwanie w Internecie doprowadziło mnie do przekonania, że ​​„APXHardness implikuje, że nie ma QPTAS dla problemu, chyba że [jakaś klasa złożoności] jest zawarta w [innej klasie złożoności]” i jest również dobrze znana! Wygląda na to, że wszyscy o tym wiedzą oprócz mnie. Niestety nie podano odniesienia do tego oświadczenia. …
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.