Pytania otagowane jako circuit-complexity

Złożoność obwodu to badanie obwodów ograniczonych przez zasoby i funkcji obliczanych przez takie obwody.

1
obwodu
Czy wiadomo, czy problem z oceną obwodu występuje w ? Co powiesz na (uniform )? N C 1 A L O g T i m e N C 1NC1NC1\mathsf{NC^1}NC1NC1\mathsf{NC^1}ALogTimeALogTime\mathsf{ALogTime}NC1NC1\mathsf{NC^1} Wiemy, że obwody o głębokości można oceniać za pomocą obwodów o głębokości gdzie jest stałą uniwersalną. Oznacza to, że obwody o …
1
Twierdzenie Adlemana o nieskończonych półkolach?
Adleman wykazały w 1978 r : Jeżeli logiczna funkcja o zmiennych może być obliczany za pomocą prawdopodobieństwa logicznego obwodu o rozmiarze , a następnie może być obliczany za pomocą deterministycznych obwód boolowski wielomianu wielkości w i ; właściwie o wielkości . BPP⊆P/polyBPP⊆P/poly\mathrm{BPP}\subseteq \mathrm{P/poly}fffnnnMMMfffMMMnnnO(nM)O(nM)O(nM) Pytanie ogólne: W stosunku do innych (boolowskich) …
2
Załamuje się przy założeniu, że
Wiadomo, że w przypadku następnie wielomian hierarchia zapada się Ď P 2 i M A = A M .N.P.⊆ P./ PO l rNP⊆P/PolyNP\subseteq P/PolyΣP.2)Σ2P\Sigma_2^{P}M.= MMA=AMMA = AM Jakie są najsilniejsze znane upadki, jeśli ?N.miXP.⊆ P./ PO l rNEXP⊆P/PolyNEXP\subseteq P/Poly
2
Jaka jest równoważna definicja mP / poli w odniesieniu do maszyny Turinga?
P / poly to klasa problemów decyzyjnych rozwiązanych przez rodzinę obwodów boolowskich wielkości wielomianowych. Alternatywnie można go zdefiniować jako wielomianową maszynę Turinga, która otrzymuje ciąg porady, który jest wielomianem wielkości w n, i który opiera się wyłącznie na rozmiarze n. mP / poli to klasa problemów decyzyjnych rozwiązanych przez rodzinę …
2
Czy można zastosować ograniczenia losowe, aby uzyskać dolną granicę dla
Istnieje wiele dobrze znanych C 0 wielkości obwód dolny związanego wyniki w oparciu o losowe ograniczeń i przełączania lematu .AC0AC0\mathsf{AC^0} Czy możemy opracować wynik zamiany lematu, aby udowodnić niższą wielkość dla obwodów TC0TC0\mathsf{TC^0} (podobnie do dolnej granicy dla AC0AC0\mathsf{AC^0} )? Czy jest jakaś nieodłączna przeszkoda w stosowaniu tego podejścia do …
1
Charaterization Complexity Circuit dla DLogTime i NLogTime
i N L o g T i m e są dwiema najmniejszymi klasami złożoności, jakie mamy. (Należy zauważyć, że w czasie logarytmicznej hierarchia l H jest równe A C 0 i są dwa pierwsze poziom L H ).DLogTimeDLogTime\mathsf{DLogTime}NLogTimeNLogTime\mathsf{NLogTime}LHLH\mathsf{LH}AC0AC0\mathsf{AC}^0LHLH\mathsf{LH} Po zapoznaniu się pytanie , staję się interesuje, czy odstęp pomiędzy tymi …
2
Czy L ma definicję obwodów?
Wiele klas złożoności zdefiniowanych za pomocą maszyn Turinga ma definicje w kategoriach jednorodnych obwodów. Na przykład P można również zdefiniować za pomocą obwodów o jednorodnych rozmiarach wielomianowych, podobnie BPP, NP, BQP itp. Można zdefiniować za pomocą obwodów jednorodnych. Czy istnieje oparta na obwodzie definicja L? Oczywistym pomysłem byłoby dopuszczenie obwodów …
2
Czy SAT jest językiem bezkontekstowym?
Rozważam język wszystkich zadowalających formuł logicznych zdań, SAT (aby upewnić się, że ma to skończony alfabet, będziemy kodować litery zdań w odpowiedni sposób [edytuj: odpowiedzi wskazały, że odpowiedź na pytanie może nie być solidna pod różne kodowania, więc trzeba być bardziej szczegółowym - patrz moje wnioski poniżej] ). Moje proste …
1
Czy obwody arytmetyczne są słabsze niż logiczne?
Niech oznacza minimalny rozmiar (niemonotonowego) arytmetycznego obwodu obliczającego dany wielomianowy wielomian i oznaczają minimalny rozmiar ( obwodu logicznego obliczającego wersję logiczną z zdefiniowane przez: A(f)A(f)A(f)(+,×,−)(+,×,−)(+,\times,-)f(x1,…,xn)=∑e∈Ece∏i=1nxeii,f(x1,…,xn)=∑e∈Ece∏i=1nxiei, f(x_1,\ldots,x_n)=\sum_{e\in E}c_e\prod_{i=1}^n x_i^{e_i}\,, B(f)B(f)B(f)(∨,∧,¬)(∨,∧,¬)(\lor,\land,\neg) fbfbf_bffffb(x1,…,xn)=⋁e∈E ⋀i:ei≠0xi.fb(x1,…,xn)=⋁e∈E ⋀i:ei≠0xi. f_b(x_1,\ldots,x_n)=\bigvee_{e\in E}\ \bigwedge_{i\colon e_i\neq 0} x_i\,. Czy znane są wielomiany dla których jest mniejsze niż ? fffB(f)B(f)B(f)A(f)A(f)A(f) Jeśli …
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.