Pytania otagowane jako cc.complexity-theory

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

1
Czy
Zdefiniuj jako klasę języków, które mogą być akceptowane przez (wielopasmową) maszynę Turinga w czasie f ( n ) + 1 . („ + 1 ” ma jedynie na celu uproszczenie notacji i uniknięcie pomyłek.) Zauważ, że nie ma O ( ⋅ ) wokół f ( n ) + 1 .D …
2
Zmniejszenie P vs. NP do SAT
W poniższym pytaniu wykorzystano pomysły z kryptografii zastosowane w teorii złożoności. To powiedziawszy, jest to pytanie teoretycznie złożone, i aby odpowiedzieć na to pytanie, nie jest wymagana żadna wiedza kryptograficzna. Celowo piszę to pytanie bardzo nieformalnie. Brakuje szczegółów, prawdopodobnie jest to nieco niepoprawnie podane. Prosimy o wskazanie poprawek w swoich …
1
Konsekwencje
Mam część próbnej próby ⊕P⊆NP⊕P⊆NP\oplus \mathbf{P} \subseteq \mathbf{NP}. Próba dowodowa polega na zmniejszeniu karpu z⊕P⊕P\oplus \mathbf{P}-kompletny problem ⊕⊕\oplus3-REGULARNA POKRYWA VERTEX do SAT. Biorąc pod uwagę sześcienny wykres GGG, redukcja generuje wzór CNF FFF posiadający obie następujące właściwości: FFF ma co najwyżej 111 spełniające zadanie. FFF jest zadowalający tylko i tylko …
1
Czy DSPACE (n) = DSPACE (1,5n)?
Z twierdzenia o hierarchii przestrzeni wiadomo, że jeśli faff można konstruować w przestrzeni, to DSPACE ( 2 f( n )2f(n)2f(n) ) nie jest równe DSPACE ( fa( n ) )f(n))f(n)) . Tutaj przez DSPACE ( fa( n ) )f(n))f(n)) mam na myśli klasę wszystkich problemów, które można rozwiązać w przestrzeni …
1
Czy twierdzenie o hierarchii przestrzeni generalizuje się do obliczeń niejednorodnych?
Pytanie ogólne Czy twierdzenie o hierarchii przestrzeni generalizuje się do obliczeń niejednorodnych? Oto kilka bardziej szczegółowych pytań: L/poly⊊PSPACE/polyL/poly⊊PSPACE/polyL/poly \subsetneq PSPACE/poly Czy dla wszystkich funkcji f (n) możliwych do zbudowania w przestrzeni f(n)f(n)f(n)jest DSPACE(o(f(n)))/poly⊊DSPACE(f(n))/polyDSPACE(o(f(n)))/poly⊊DSPACE(f(n))/polyDSPACE(o(f(n)))/poly \subsetneq DSPACE(f(n))/poly ? Dla jakich funkcji h(n)h(n)h(n) wiadomo, że: dla wszystkich możliwych do zbudowania przestrzeni f(n)f(n)f(n) , …
1
Sparametryzowana złożoność włączenia zwykłych języków
Interesuje mnie klasyczny problem REGULARNE WŁĄCZENIE JĘZYKA. Biorąc pod uwagę wyrażenie regularne , oznaczamy przez L ( E ) powiązany z nim język regularny. (Wyrażenia regularne są na stałej alfabetu Ď z unii operacji, Kleene-gwiazdkowe i konkatenacji).miEEL ( E)L(E)L(E)ΣΣ\Sigma Dane wejściowe: dwa wyrażenia regularne i E 2 Pytanie: Czy to …
1
Generowanie „nieskończonej” losowości ze stałej liczby źródeł
Ostatnio natknąłem się na artykuł Coudrona i Yuena na temat ekspansji losowości za pomocą urządzeń kwantowych. Głównym rezultatem pracy jest to, że możliwe jest wygenerowanie „nieskończonej” losowości ze stałej liczby źródeł (to znaczy liczba wygenerowanych bitów losowych zależy tylko od liczby rund protokołu, a nie od liczby źródeł ). Naiwnie …
3
Złożoność obliczania parzystości odczytu dwukrotnego przeciwnego do wzoru CNF (
W dwukrotnej, przeciwnej do odczytu formule CNF, każda zmienna pojawia się dwukrotnie, raz dodatnia, a raz ujemna. Jestem zainteresowany w problem, który polega na obliczaniu parytetu liczby spełniających zadania o przeciwnej wzoru CNF odczytu dwukrotnie.⊕ Rtw-Opp-CNF⊕Rtw-Opp-CNF\oplus\text{Rtw-Opp-CNF} Nie udało mi się znaleźć odniesienia do złożoności takiego problemu. Najbliższe, jakie udało mi …
1
W jakim stopniu zdolność obliczeniowa trudnych zadań pomaga w rozwiązywaniu łatwych zadań
Krótko mówiąc, pytanie brzmi: w jakim stopniu zdolność obliczeniowa do trudnych zadań naprawdę pomaga w rozwiązywaniu łatwych zadań. (Mogą istnieć różne sposoby uczynienia tego pytania interesującym i nietrywialnym, a oto jedna z takich prób). Pytanie 1: Rozważ obwód rozwiązywania SAT dla formuły z n zmiennymi. (Lub do znalezienia cyklu hamiltonowskiego …
4
Czy istnieje algorytmiczna analiza matematyczna?
Istnieją teorie grafów algorytmicznych / teoria liczb / kombinatoryka / teoria informacji / teoria gier. Czy istnieje algorytmiczna analiza matematyczna? Według wiki analiza matematyczna obejmuje teorie różniczkowania, całkowania, miary, limitów, szeregów nieskończonych i funkcji analitycznych. Można skupić się na analizie rzeczywistej (wiki), która zajmuje się liczbami rzeczywistymi i funkcjami wartości …
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.