Teoretyczne informatyka

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

1
Jaki jest najprostszy model obliczeniowy, dla którego problem pustki jest nierozstrzygalny?
Jaki jest najprostszy model obliczeniowy, dla którego problem pustki jest nierozstrzygalny? Problem pustki dla modelu obliczeniowego (np. Automat skończony, automat przemienny, automat kwantowy z ograniczeniem błędu z licznikiem, deterministyczny LBA itp.) Polega na ustaleniu, czy dla danej takiej maszyny język rozpoznawany / definiowany przez tę maszynę jest pusty. Tutaj opis …
1
Twardość APX oznacza brak QPTAS?
Szybkie wyszukiwanie w Internecie doprowadziło mnie do przekonania, że ​​„APXHardness implikuje, że nie ma QPTAS dla problemu, chyba że [jakaś klasa złożoności] jest zawarta w [innej klasie złożoności]” i jest również dobrze znana! Wygląda na to, że wszyscy o tym wiedzą oprócz mnie. Niestety nie podano odniesienia do tego oświadczenia. …
3
Jak iterować po wektorach w kolejności prawdopodobieństwa na małej przestrzeni
Rozważmy wymiarowy wektor gdzie . Dla każdego wiemy i załóżmy, że są niezależne. Wykorzystując te prawdopodobieństwa, czy istnieje skuteczny sposób na iterację binarnych wektorów wymiarowych w kolejności od najbardziej prawdopodobnego do najmniej prawdopodobnego (z dowolnymi wyborami wiązań) z wykorzystaniem przestrzeni podliniowej w wielkości wyjściowej? v v i ∈ { 0 …
1
jako wyrocznia
Czy N P.N P.∩c o N P= N P.N.P.N.P.∩dooN.P.=N.P.\mathsf{NP^{NP \,\cap\, coNP}=NP}trzymać? Najwyraźniej N P.N P.≠ N P.N.P.N.P.≠N.P.\mathsf{NP^{NP}\neq NP} , ale wydaje mi się, że N P ∩ c o N PN.P.∩dooN.P.\mathsf{NP\cap coNP} jest „deterministyczna”, co pozwala mi wierzyć, że to prawda. Czy istnieje prosty dowód (a może tylko z definicji)?
3
Kiedy stosować lemat Johnson-Lindenstrauss zamiast SVD?
Lemat Johnsona-Lindenstraussa pozwala reprezentować punkty w przestrzeni o dużych wymiarach w punktach o niższych wymiarach. Podczas znajdowania najlepiej dopasowanych mniejszych wymiarów, standardową techniką jest znalezienie rozkładu wartości w liczbie pojedynczej, a następnie wzięcie podprzestrzeni wygenerowanej przez największe wartości w liczbie pojedynczej. Kiedy warto zastosować Johnson-Lindenstrauss zamiast SVD?
1
Algebraicznie zwarte kategorie
Przeczytałem artykuł Freyda „Algebraicznie kompletne kategorie” w słynnym Como90 i mam dwa pytania dotyczące pojęcia zwartości algebraicznej zdefiniowanej w tym artykule. (Jeśli nie znasz tej definicji, oto ona: Kategoria nazywa się zwartą algebraicznie, jeśli każdy endofunkor ma początkową algebrę i końcową koalgebrę, które są kanonicznie izomorficzne.) Jakie są przykłady kategorii …
3
NP-pełna właściwość graficzna, która jest dziedziczna, ale nie addytywna?
Właściwość wykresu jest nazywana dziedziczną, jeśli zostanie zamknięta w odniesieniu do usuwania wierzchołków (tj. Wszystkie indukowane podgrupy dziedziczą właściwość). Właściwość graf nazywa się addytywną, jeśli jest zamknięta w odniesieniu do przyjmowania rozłącznych związków. Nie jest trudno znaleźć właściwości dziedziczne, ale nie addytywne. Dwa proste przykłady: \;\;\;(1) Wykres jest kompletny. \;\;\;(2) …
1
Decydująca teoria asymptotycznego wzrostu
Jakie są znane granice rozstrzygalności porównania szybkości wzrostu funkcji z ? Mam na myśli rozstrzygalność pytań takich jak „Czy x x ∼ 2 ⌊ x lg ( x + 2 ) ⌋ ?” lub „Czy 2 lg ∗ x ∈ O ( lg lg x ) ?”.N→NN→N\mathbb{N} \to \mathbb{N}xx∼2⌊xlg(x+2)⌋xx∼2⌊xlg⁡(x+2)⌋x^x \sim …
3
Wybierz w połączeniu uporządkowanych tablic: Już znasz?
Szukam odniesień bibliograficznych dla następującego algorytmu / problemu: nazwałem go „BiSelect” lub „t-ary Select” lub „Select in Union of Sorted Arrays”, ale myślę, że został wprowadzony wcześniej pod inną nazwą? Problem Rozważ następujący problem: Biorąc pod uwagę kkk rozłożonych tablic posortowanych , o odpowiednich rozmiarach , oraz liczbę całkowitą , …
1
Kolejka liczb całkowitych priorytetowych z zależnym od dystrybucji deleteMin
Czy w kolejce liczb całkowitych priorytetowych, która używa słów spacji z następującymi operacjami, wszystko w najgorszym przypadku i bez dostępu do losowości:O(n)O(n)O(n) createEmptyQueuew dla pewnej stałej c .O(lgcU)O(lgcU)O(lg^c U)ccc insertw .O(1)O(1)O(1) deleteMinO(δmin)O(δmin)O(\delta_{\min})δminδmin\delta_{\min} Ponadto, gdy klucz zostanie poddany a , wszystkie dalsze wstawki mają .kkkdeleteMin>k>k> k Powiązana praca: „Szybkie lokalne wyszukiwania …
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.