Pytania otagowane jako cc.complexity-theory

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

4
Problemy, które w praktyce można rozwiązać w sposób sprzeczny z intuicją?
Niedawno przeszedłem przez bolesną zabawę polegającą na nieformalnym wyjaśnianiu koncepcji złożoności obliczeniowej młodemu utalentowanemu samoukiem, programistowi, który nigdy wcześniej nie odbył formalnego kursu algorytmów ani złożoności. Nic dziwnego, że wiele pojęć początkowo wydawało się dziwnych, ale miało sens w niektórych przykładach (PTIME, trudność, niezliczalność) , podczas gdy inne wydają się …
3
Czy wpisane obliczenia lambda wyrażają * wszystkie * algorytmy poniżej określonej złożoności?
Wiem, że złożoność większości odmian kalkulatorów lambda bez prymitywu kombinatora Y jest ograniczona, tzn. Można wyrazić tylko funkcje o ograniczonej złożoności, przy czym granica staje się większa wraz ze wzrostem ekspresyjności systemu typów. Pamiętam, że np. Rachunek konstrukcji może wyrażać co najwyżej podwójnie wykładniczą złożoność. Moje pytanie dotyczy tego, czy …
1
Czy P jest równe przecięciu wszystkich wielobiegunowych klas czasowych?
Nazwijmy funkcję wielobiegunową, jeśli dla każdego c> 0 .f(n)f(n)f(n) c > 0limn→∞nc/f(n)=0limn→∞nc/f(n)=0\lim_{n\rightarrow\infty} n^c/f(n)=0c>0c>0c>0 Oczywiste jest, że dla każdego języka L∈PL∈PL\in {\mathsf P} utrzymuje, że L∈DTIME(f(n))L∈DTIME(f(n))L\in {\mathsf {DTIME}}(f(n)) dla każdego superminomalnego ograniczenia czasowego f(n)f(n)f(n) . Zastanawiam się, czy odwrotność tego stwierdzenia jest również prawdą? To znaczy, jeśli znamy L∈DTIME(f(n))L∈DTIME(f(n))L\in {\mathsf {DTIME}}(f(n)) …
2
kompletność rozpoznania różnicy dwóch permutacji
Shor stwierdził w swoim komentarzu do odpowiedzi anonimowego łosia na to pytanie. Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym? , To jest -Complete do określenia różnicę dwóch permutacji. Niestety, nie widzę prostą redukcję od problemu sumy permutacji i warto mieć N P zmniejszenie -completeness dla problemu różnicy permutacji.NPNPNPNPNPNP …
1
Algorytmy i teoria złożoności strukturalnej
Wiele ważnych wyników w teorii złożoności obliczeniowej, a zwłaszcza teoria złożoności „strukturalnej”, ma interesującą właściwość, którą można rozumieć jako zasadniczo wynikającą (jak widzę ...) z wyników algorytmicznych, dającą skuteczny algorytm lub protokół komunikacyjny dla niektórych problem. Należą do nich: IP = PSPACE wynika z wydajnego przestrzennie algorytmu rekurencyjnego symulującego interaktywne …
2
Obwody dolne granice i złożoność Kołmogorowa
Rozważ następujące uzasadnienie: Niech oznacza złożoność Kołmogorowa ciągu . Twierdzenie Chaitina o niekompletności tak mówiK(x)K(x)K(x)xxx dla jakiejkolwiek spójnej i wystarczająco silny system formalny , istnieje stała (zależnie tylko od formalnego systemu i jego języka) tak, że dla każdej struny , nie może udowodnić, że .SSSTTTxxxSSSK(x)≥TK(x)≥TK(x) \geq T Niech będzie funkcją …
1
Czy
Czy istnieje jakakolwiek prawdopodobna hipoteza złożoności / kryptografii, która wyklucza możliwość, że obwody wielomianowe mają rozmiar podwykładniczy (tj. z ) ograniczoną głębokością ( ) obwody? ϵ&lt;1d=O(1)2)O ( nϵ)2O(nϵ)2^{O(n^\epsilon)}ϵ &lt; 1ϵ&lt;1\epsilon<1re= O ( 1 )d=O(1)d = O(1) Wiemy, że każdą funkcję obliczalną przez obwód można obliczyć na podstawie obwodu głębokości (używając …
2
Czy dodawanie można przeprowadzić na głębokości mniejszej niż 5?
Stosując algorytm przenoszenia patrzeć w przyszłość możemy obliczyć dodatek za pomocą wielomianu głębokość rozmiar 5 (lub 4?) C 0 rodzinę obwodu. Czy można zmniejszyć głębokość? Czy możemy obliczyć dodanie dwóch liczb binarnych przy użyciu wielomianowej rodziny obwodów o głębokości mniejszej niż uzyskana za pomocą algorytmu carry look forward?AC0AC0AC^0 Czy są …
2
Czy obwody AND i OR P-są kompletne?
Bramka AND &amp; OR jest bramką, która ma dwa wejścia i zwraca ich AND oraz OR. Czy obwody wykonane tylko z bramki AND &amp; OR, bez fanouta, mogą wykonywać dowolne obliczenia? Mówiąc ściślej, czy obszar logiczny obliczeń wielomianowych można zredukować do obwodów AND i OR? Moja motywacja do rozwiązania tego …
3
Od ekstraktorów do generatorów pseudolosowych?
Luca Trevisan pokazał, ile konstrukcji generatorów pseudolosowych można uznać za konstrukcje ekstraktorów: http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf Czy istnieje sensowna rozmowa? Tj. Czy „naturalne” konstrukcje ekstraktorów można traktować jako konstrukcje pseudolosowych generatorów (PRG)? Konstrukcje ekstraktorów wydają się odpowiadać rozkładom na PRG (tak, że żadnemu wyróżniającemu nie uda się rozróżnić dla prawie wszystkich z nich). …
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.