Pytania otagowane jako cc.complexity-theory

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

3
Wyjaśnienie w stylu Wikipedii teorii złożoności geometrycznej
Czy ktoś może przedstawić zwięzłe wyjaśnienie podejścia GCT Mulmuleya, zrozumiałe dla osób nie będących ekspertami? Wyjaśnienie, które byłoby odpowiednie dla strony Wikipedii na ten temat (która jest w tej chwili krótka). Motywacja: „Czytam” książkę Scotta Aaronsona Quantum Computing od czasów Demokryta z moim przyjacielem, który jest badaczem teorii strun. W …
8
Najlepsze górne granice na SAT
W innym wątku Joe Fitzsimons zapytał o „najlepsze obecne dolne granice 3SAT”. Chciałbym pójść w drugą stronę: jakie są najlepsze obecne górne granice 3SAT? Innymi słowy, jaka jest złożoność czasowa najbardziej wydajnego solvera SAT? W szczególności, czy można sobie wyobrazić algorytm subwykładniczy (a jednak super-wielomianowy) dla SAT?
22
Jakie znasz hierarchie i / lub twierdzenia dotyczące hierarchii?
Obecnie piszę ankietę na temat twierdzeń hierarchicznych dotyczących TCS. Szukając powiązanych artykułów zauważyłem, że hierarchia jest fundamentalną koncepcją nie tylko w TCS i matematyce, ale w wielu naukach, od teologii i socjologii po biologię i chemię. Widząc, że ilość informacji jest ogromna, mam nadzieję, że mógłbym poprosić o pomoc tę …
12
Gröbner bazuje w TCS?
Czy ktoś wie o ciekawych zastosowaniach baz Gröbnera w teoretycznej informatyce? Podstawy Gröbnera są używane do rozwiązywania wielowymiarowych równań wielomianowych, co jest ogólnie trudnym problemem NP. Zastanawiałem się, czy użyto niektórych możliwych do rozwiązania specjalnych przypadków w celu zapewnienia wydajnych algorytmów / konstrukcji / dowodów w obszarach TCS lub powiązanych …
3
Konsekwencje quasi-wielomianowego algorytmu czasowego dla problemu izomorfizmu grafowego
Problemem wykres Izomorfizm (Gl) jest prawdopodobnie najbardziej znanym kandydatem na NP pośredniego problemu. Najbardziej znanym algorytmem jest algorytm subwykładniczy z czasem działania . Wiadomo, że GI nie jest -kompletny, chyba że hierarchia wielomianowa się załamie.2O(nlogn√)2O(nlog⁡n)2^{O(\sqrt{n \log n})}NPNP\mathsf{NP} Jakie byłyby teoretyczne konsekwencje złożoności quasi-wielomianowego algorytmu czasowego dla problemu grafowego izomorfizmu? Czy …
5
Przytulne dzielnice „P” i „NP-hard”
Niech będzie zadaniem algorytmicznym. (Może to być problem decyzyjny, problem optymalizacji lub inne zadanie.) Nazwijmy X „po stronie wielomianowej”, jeśli wiadomo, że założenie, że X jest trudne NP, oznacza, że ​​załamuje się wielomianowa hierarchia. Nazwijmy X „po stronie NP”, jeśli wiadomo, że X przyjmuje algorytm wielomianowy, który implikuje załamanie się …
3
Jakie są powody, dla których badacze geometrii obliczeniowej preferują model BSS / real-RAM?
tło Obliczenia na liczbach rzeczywistych są bardziej skomplikowane niż obliczenia na liczbach naturalnych, ponieważ liczby rzeczywiste są obiektami nieskończonymi i istnieje niezliczona liczba liczb rzeczywistych, dlatego liczb rzeczywistych nie można wiernie przedstawić za pomocą ciągów skończonych nad skończonym alfabetem. W przeciwieństwie do klasycznego obliczania ciągów skończonych, w którym różne modele …
3
Czy problem faktoryzacji liczb całkowitych jest trudniejszy niż faktoryzacja RSA:
To jest cross-post z math.stackexchange. Niech FACT oznaczają problemu faktoringowej całkowitą: podany znaleźć liczb pierwszych p i ∈ N , a całkowite e I ∈ N , tak, że N = Π k i = 0 p e ı ı .n∈N,n∈N,n \in \mathbb{N},pi∈N,pi∈N,p_i \in \mathbb{N},ei∈N,ei∈N,e_i \in \mathbb{N},n=∏ki=0peii.n=∏i=0kpiei.n = \prod_{i=0}^{k} p_{i}^{e_i}. …
2
Program GCT Mulmuleya
Czasami twierdzi się, że teoria złożoności geometrycznej Ketana Mulmuleya jest jedynym wiarygodnym programem do rozstrzygania otwartych pytań teorii złożoności, takich jak pytanie P vs. NP. Było wiele pozytywnych komentarzy od słynnych teoretyków złożoności na temat programu. Według Mulmuleya osiągnięcie pożądanych rezultatów zajmie dużo czasu. Wejście w ten obszar nie jest …
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.