Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

2
Wybierz dwie liczby, które sumują się do , używając sublinearnego czasu zapytania
Oto problem najbliższego sąsiada. Biorąc pod uwagę liczby rzeczywiste (bardzo duże !), Plus cel rzeczywisty , znajdź i których SUMA jest najbliższe . Umożliwiamy rozsądne wstępne przetwarzanie / indeksowanie (do ), ale w czasie zapytania (dane ) wynik powinien zostać zwrócony bardzo szybko (np. czas).za1, ... ,zana1,…,ana_1, \ldots, a_nnnnpppzajaaia_izajotaja_jpppza1, ... …
1
Znalezienie optymalnej równoległości z ogólnego ważonego niekierowanego wykresu
Rozwiązuję problem „mieszania” zestawów nakładających się obrazów. Te zestawy mogą być reprezentowane przez niekierowany ważony wykres, taki jak ten: Każdy węzeł reprezentuje obraz. Nakładające się obrazy są połączone krawędzią. Ciężar krawędzi reprezentuje wielkość obszaru nakładania się ( wcześniejsze połączenie większego nakładania prowadzi do lepszej ogólnej jakości ). Algorytm ogólnie usuwa …
2
Jaki jest cel abstrakcyjnej interpretacji w językach programowania?
Próbuję teraz lepiej zrozumieć, czym jest „abstrakcyjna interpretacja” w językach programowania. Znalazłem dobry rozdział w książce, który wyjaśnia pomysł rozszerzenia dziedziny o najmniej ustalony element, cztery aksjomaty, które dają stały punkt dla funkcji ciągłej i tak dalej. Rozumiem te szczegóły techniczne (choć nie jestem całkiem pewien, do czego dokładnie odnosi …
2
Czy możliwa jest meta-nierozstrzygalność?
Istnieją problemy, które można rozstrzygnąć, niektóre są nierozstrzygalne, istnieje możliwość rozstrzygnięcia itp. W tym przypadku zastanawiam się, czy problem może być nierozstrzygalny. Oznacza to (przynajmniej w mojej głowie), że nie możemy stwierdzić, czy jest to rozstrzygalne, czy nie. Być może wiadomo, że rozstrzygalność jest nierozstrzygalna (wszystko jest meta-nierozstrzygalne) i nie …
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
Anulowanie i wyznacznik
Algorytm Berkowitza zapewnia obwód wielomianowy o głębokości logarytmicznej do wyznaczania macierzy kwadratowej z wykorzystaniem mocy macierzy. Algorytm domyślnie wykorzystuje anulowanie. Czy anulowanie jest niezbędne do uzyskania obwodu wielomianowego o głębokości logarytmicznej lub liniowej w celu obliczenia wyznacznika (i każdego możliwego najlepszego obwodu na stałe)? Czy istnieją dolne granice w pełni …
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
Czy może istnieć wyjątkowo duży ukryty podzbiór problemów wielomianowo możliwych do rozwiązania w ramach problemów NP-Complete?
Załóżmy, że P! = NP. Wiemy, że w każdej chwili możemy wykonać proste instancje 3-SAT. Możemy również wygenerować coś, co uważamy za trudne wystąpienie (ponieważ nasze algorytmy nie potrafią ich szybko rozwiązać). Czy jest coś, co przeszkadza, by zbiór twardych instancji był arbitralnie mały, o ile dla dowolnej wielkości instancji …
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 …
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.