Pytania otagowane jako cc.complexity-theory

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

2
Konsekwencje OWF dla złożoności
Powszechnie wiadomo, że istnienie funkcji jednokierunkowych jest konieczne i wystarczające dla dużej części kryptografii (podpisy cyfrowe, generatory pseudolosowe, szyfrowanie kluczem prywatnym itp.). Moje pytanie brzmi: jakie są teoretyczne konsekwencje istnienia funkcji jednokierunkowych? Na przykład sugerują to OWFN P ≠ PN.P.≠P.\mathsf{NP}\ne\mathsf{P}, B P P = PbP.P.=P.\mathsf{BPP}=\mathsf{P}, i C Z K = …
3
Złożoność SMT z jedną alternatywą
Szukam złożoności spełniania formuły ∀y1,…,yn,∃x1,…,xm,ϕ∀y1,…,yn,∃x1,…,xm,ϕ\forall y_1, \dots,y_n, \exists x_1,\dots,x_m, \phi lub o wzorze ∃x1,…,xm∀y1,…,yn,ϕ∃x1,…,xm∀y1,…,yn,ϕ \exists x_1,\dots,x_m \forall y_1, \dots,y_n,\phi gdzie ϕϕ\phi jest formuła formularza: ϕ:=ϕ∧ϕ | ¬ϕ | ϕ→ϕ | ψϕ:=ϕ∧ϕ | ¬ϕ | ϕ→ϕ | ψ\phi:= \phi \wedge\phi ~| ~\neg \phi ~| ~ \phi\to \phi~| ~\psi ψ:=t>t | t=tψ:=t>t …
2
Ograniczona formuła Monotone 3CNF: liczenie spełniających się zadań (oba modulo
Rozważ formułę Monotone 3CNF mającą oba następujące dodatkowe ograniczenia: Każda zmienna występuje dokładnie w klauzulach.2)22 Biorąc pod uwagę dowolne klauzule, mają one maksymalnie zmienną.2)22111 Chciałbym wiedzieć, jak ciężko jest liczyć satysfakcjonujące zadania takiej formuły. Aktualizacja 06.04.2013 12:55 Chciałbym również wiedzieć, jak trudne jest ustalenie parytetu liczby satysfakcjonujących zadań. Aktualizacja 11.04.2013 …
2
Czy adiabatyczne obliczenia kwantowe są tak potężne jak model obwodowy?
Znaczna część literatury obliczeń kwantowych koncentruje się na modelu obwodu. Adiabatyczne obliczenia kwantowe nie polegają na zastosowaniu sekwencji operatorów jednostkowych, ale na zmianie zależnego od czasu hamiltonianu. Szukam wglądu w którekolwiek z poniższych. Czy adiabatyczne obliczenia kwantowe są tak potężne jak model obwodowy, czy też są z natury mniej wydajne? …
3
Znajdź pozostałą część dużego stałego wielomianu po podzieleniu przez niewielki nieznany wielomian
Załóżmy, że działamy w polu skończonym. Otrzymujemy duży stały wielomian p (x) (powiedzmy stopnia 1000) nad tym polem. Ten wielomian jest znany wcześniej i możemy wykonywać obliczenia przy użyciu dużej ilości zasobów w „fazie początkowej”. Wyniki te mogą być przechowywane w stosunkowo małych tabelach przeglądowych. Pod koniec „fazy początkowej” otrzymamy …
1
Mogą
Pozwolić ATISP(f(n),g(n))ATISP(f(n),g(n))\mathsf{ATISP}(f(n), g(n)) być klasą języków ustaloną przez naprzemienne maszyny Turinga, które zatrzymują się w czasie f(n)f(n)f(n) używając przestrzeni g(n)g(n)g(n). PozwolićAALTSP(f(n),g(n))AALTSP(f(n),g(n))\mathsf{AALTSP}(f(n), g(n)) być klasą języków ustaloną przez naprzemienne używanie maszyn Turinga f(n)f(n)f(n) alternacje i przestrzeń g(n)g(n)g(n). Ruzzo udowodnił , żeNCk=ATISP(logkn,logn)NCk=ATISP(logk⁡n,log⁡n)\mathsf{NC}^k = \mathsf{ATISP}(\log^k n, \log n). On też to pokazałNCk⊆AALTSP(logkn,logn)⊆NCk+1NCk⊆AALTSP(logk⁡n,log⁡n)⊆NCk+1\mathsf{NC}^k \subseteq …
2
Jak możemy wyrazić „
Zamknięte. To pytanie jest nie na temat . Obecnie nie przyjmuje odpowiedzi. Chcesz poprawić to pytanie? Zaktualizuj pytanie, aby było tematem wymiany stosów teoretycznych w informatyce. Zamknięte 7 lat temu . Jak możemy wyrazić „ ” jako formułę pierwszego rzędu?P.= PS.P.A C.miP=PSPACEP=PSPACE Który poziom hierarchii arytmetycznej zawiera tę formułę (i …
1
(Kryptograficzne) problemy do rozwiązania w wielomianowej liczbie kroków arytmetycznych
W artykule Adi Shamira [1] z 1979 r. Pokazuje, że faktoring można wykonać w wielomianowej liczbie kroków arytmetycznych . Fakt ten został powtórzony i dlatego zwrócił moją uwagę w niedawnej pracy Borweina i Hobarta [2] w kontekście programów liniowych (SLP). Ponieważ byłem raczej zaskoczony, gdy to przeczytałem, mam następujące pytanie: …
1
„Informacje możliwe do zweryfikowania”: czy jest to znana koncepcja?
Poniższe wydaje mi się naturalną definicją i zastanawiam się, czy gdzieś to zbadano Rozważać X⊂2{0,1}∗X⊂2{0,1}∗\mathsf{X} \subset 2^{\lbrace 0, 1 \rbrace^*}zestaw języków. NastępnieK⊂{0,1}ωK⊂{0,1}ωK \subset \lbrace 0, 1 \rbrace^\omega nazywa się "XX\mathsf{X}-weryfikowalne informacje ”, gdy są L∈XL∈XL \in \mathsf{X} św (i) Biorąc pod uwagę x∈Lx∈Lx \in L, każdy prefiks xxx jest w …
2
Wyniki dotyczące złożoności funkcji rekurencyjnych o niższych elementach?
Zaintrygowany ciekawym pytaniem Chrisa Presseya na temat funkcji elementarno-rekurencyjnych badałem więcej i nie mogłem znaleźć odpowiedzi na to pytanie w Internecie. Te podstawowe funkcje rekurencyjne odpowiadają dobrze wykładniczemu hierarchii .DTIME (2)n) ∪ DTIME (2)2)n) ∪ ⋯DTIME(2n)∪DTIME(22n)∪⋯\text{DTIME}(2^n) \cup \text{DTIME}(2^{2^n}) \cup \cdots Z definicji wydaje się proste, że problemy decyzyjne rozstrzygalne (termin?) …
1
Optymalność algorytmu Grovera z dużym prawdopodobieństwem powodzenia
Dobrze wiadomo, że złożoność kwantowej kwerendy błędu ograniczonego funkcji to . Teraz pytanie brzmi: czy chcemy, aby nasz algorytm kwantowy odniósł sukces dla każdego wejścia z prawdopodobieństwem a nie ze zwykłą . Jeśli chodzi o jakie byłyby odpowiednie górne i dolne granice?O R (x1,x2), ... ,xn)OR(x1,x2,…,xn)OR(x_1,x_2,\ldots, x_n)Θ (n--√)Θ(n)\Theta(\sqrt{n})1 - ϵ1−ϵ1-\epsilon2 …
1
Połączenie między PCP a L = SL
Książka Arory i Baraka zawiera uwagi do rozdziału na temat PCP Zauważamy, że ogólna strategia Dinura przypomina nieco zygzakowatą konstrukcję wykresów ekspanderów i deterministyczny algorytm przestrzeni logicznej Reingolda dla połączeń bezkierunkowych opisany w rozdziale 20, co sugeruje, że więcej połączeń oczekuje na nawiązanie między tymi różnymi obszarami badań. (str. 494) …
1
FO-uniform AC0 z pewnym orzeczeniem
Moje pytanie dotyczy teorii modeli skończonych / złożoności opisowej, więc FO(R)FO(R)FO(R) będzie oznaczać „pierwszy rząd nad skończonymi słowami binarnymi, przy użyciu predykatów Rs i jednoargumentowego predykatu P true na pozycji 1 w słowie”. Chciałbym wiedzieć, czy jest jakakolwiek caracterization FO(&lt;,R)FO(&lt;,R)FO(<,R) z R dowolnym orzeczeniem NrNr\mathbb N^rdla jakiegoś r? Na przykład …
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.