Pytania otagowane jako reference-request

Prośba o referencję jest wykorzystywana, gdy autor musi wiedzieć o pracy związanej z pytaniem.

2
Wyliczanie płaskich wykresów ograniczonej szerokości poprzecznej
Szukam odniesień do następującego problemu: biorąc pod uwagę liczby całkowite i , wyliczyć wszystkie nieizomorficzne wykresy płaskie na wierzchołkach i szerokości linii . Interesują mnie zarówno wyniki teoretyczne, jak i praktyczne, ale przede wszystkim praktyczne algorytmy, które można kodować i uruchamiać dla możliwie dużych wartości i (pomyśl i ). Jeśli …
1
Zgodność pierwszego rzędu bez modeli skończonych
Wiemy z twierdzenia Kościoła, że ​​określenie satysfakcji pierwszego rzędu jest ogólnie nierozstrzygalne, ale istnieje kilka technik, które można zastosować do ustalenia satysfakcji pierwszego rzędu. Najbardziej oczywiste jest poszukiwanie modelu skończonego. Istnieje jednak szereg instrukcji w logice pierwszego rzędu, które możemy wykazać, że nie mają modeli skończonych. Na przykład każda dziedzina, …
2
Dokładna złożoność problemu w
Pozwolić xi∈{−1,0,+1}xi∈{−1,0,+1}x_i \in \{-1,0,+1\} dla i∈{1,…,n}i∈{1,…,n}i \in \{1,\ldots,n\}, z obietnicą, że x=∑ni=1xi∈{0,1}x=∑i=1nxi∈{0,1}x = \sum_{i=1}^n{x_i} \in \{0,1\} (gdzie suma się skończyła ZZ\mathbb{Z}). Jaka jest złożoność ustalenia, czyx=1x=1x = 1? Zauważ, że w trywialny sposób leży problem ∩m≥2AC0[m]∩m≥2AC0[m]\cap_{m \geq 2}{\mathsf{AC}^0[m]} ponieważ x≡1modmx≡1modmx \equiv 1\bmod{m}iff . Pytanie brzmi: czy problem leży w ? …
1
Kto ukuł termin „empiryczna entropia”?
Wiem o pracy Shannona z entropią, ale ostatnio pracowałem nad zwięzłymi strukturami danych, w których entropia empiryczna jest często używana jako część analizy pamięci. Shannon zdefiniował entropię informacji wytwarzanej przez dyskretne źródło informacji jako , gdzie jest prawdopodobieństwem wystąpienia zdarzenia , np. Wygenerowany określony znak, i istnieją możliwe zdarzenia.−∑ki=1pilogpi−∑i=1kpilog⁡pi-\sum_{i=1}^k p_i …
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 = …
2
Równania diofantyczne i klasy złożoności
Liniowa diofantycznego RÓWNANIA (podane liczbami naturalnymi, , czy są liczbami naturalnymi, i y takie, że ax + by + c = 0 ?) To rozpuszczalny w czasie wielomianowym.a , b , cza,b,doa, b, cxxxyyya x + b y+ c = 0zax+by+do=0ax + by + c = 0 QUADRATIC DIOPHANTINE EQUATIONS …
1
Kiedy strategie -Nash Equilibrium zbiegają się ze strategiami Nash Equilibrium?
Równowagi Nasha ogólnie nie można obliczyć. -Nash równowaga jest zbiorem strategii, gdzie podane strategie rywalek, każdy gracz uzyska w ciągu maksymalnej możliwej oczekiwanego wypłat. Znalezienie równowagi Nash, biorąc pod uwagę i grę, jest .ϵϵ\epsilonϵϵ\epsilonϵϵ\epsilonϵϵ\epsilonP P A DPPAD\mathsf{PPAD} Idąc ściśle za definicjami, wydaje się, że nie ma szczególnego powodu, aby sądzić, …
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 …
1
Czy linearyzowalność jest równoważna z problemem konsensusu?
We wstępie tego artykułu Ostatecznie linearyzowalne obiekty wspólne (PODC'10) autorzy przedstawili następujące oświadczenie bez odniesień: Linearyzowalność można jednak osiągnąć tylko wtedy, gdy możliwe jest rozwiązanie konsensusu. Tutaj linearyzowalność jest najsilniejszą znaną właściwością spójności wspólnych obiektów, co zaproponowano w artykule Linearyzowalność: warunek poprawności dla współbieżnych obiektów . Mylę się co do …
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? …
1
Na
Wiemy to L⊆NL⊆P⊆NPL⊆NL⊆P⊆NP\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}. Z twierdzenia SavitchaNL⊆L2NL⊆L2\mathcal{N\!L}\subseteq\mathcal{L}^2, a od Space Hierarchy Teorem, L≠L2L≠L2\mathcal{L}\neq\mathcal{L}^2. Ponieważ nie wiemy, czyL≠PL≠P\mathcal L\neq\mathcal Pnie wiemy czy L2⊆PL2⊆P\mathcal L^2\subseteq\mathcal Pczy wiemy o tym L2⊈PL2⊈P\mathcal L^2\not\subseteq\mathcal P? Czy ktoś próbował udowodnić, że ? Jakie są najnowsze wyniki lub wysiłki w ten sposób? Próbowałem napisać ankietę na ten …
2
Certyfikowany kompilator i optymalizacje w Coq / Agda
Interesują mnie sprawdzone kompilatory sformalizowane w teorii typów Martina-Löfa, tj. Coq / Agda. W tej chwili napisałem przykład małej zabawki. Dzięki temu mogę udowodnić, że moje optymalizacje są prawidłowe. Na przykład można wyeliminować dodawanie zerowe, tzn. Wyrażenia takie jak „x + 0”. Czy istnieją optymalizacje, które są trudne do przeprowadzenia …
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.