Teoretyczne informatyka

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

1
Dolne granice funkcji progowej
W złożoności drzewa decyzyjnego funkcji boolowskiej bardzo dobrze znaną metodą dolnej granicy jest znalezienie (przybliżonego) wielomianu reprezentującego funkcję. Paturi podał charakterystykę symetrycznych funkcji boolowskich (częściowych i całkowitych) pod względem oznaczonej ilościΓΓ\Gamma: Twierdzenie ( Paturi ): Niechfff być dowolną niestałą funkcją symetryczną i oznaczać fk=f(x)fk=f(x)f_k=f(x) kiedy |x|=k|x|=k|x|=k (tj. masa młota wynosząca …
1
Czy istnieje wielomianowy rozmiar CFG opisujący ten skończony język?
Czy istnieją permutacje i wielkość wielomianowa (w ) gramatyka bezkontekstowa opisująca język skończony zamiast alfabetu ?π1,π2π1,π2\pi_1,\pi_2|w|=n|w|=n|w|=n{wπ1(w)π2(w)}{wπ1(w)π2(w)}\{w \pi_1(w) \pi_2(w)\}{0,1}{0,1}\{0,1\} AKTUALIZACJA: Dla jednej permutacji jest to możliwe. jest odwróceniem lub względnie niewielką modyfikacją odwrócenia.ππ\piππ\pi
2
Próg w pełni homomorficzne kryptosystemy
ostatnio Craig Gentry opublikował pierwszy schemat szyfrowania klucza publicznego (na przestrzeni tekstu jawnego {0,1}), który jest w pełni homomorficzny, co oznacza, że ​​można skutecznie i kompaktowo oceniać AND i XOR na zaszyfrowanych tekstach jawnych bez znajomości tajnego klucza odszyfrowywania. Zastanawiam się, czy istnieje jakiś oczywisty sposób na przekształcenie tego kryptosystemu …
1
Potężne algorytmy, które są zbyt trudne do wdrożenia - jak się upewnić, że mają rację?
Odnoszę się tutaj do pytania: potężne algorytmy zbyt złożone, aby je zaimplementować . Jeśli algorytm jest potężny, ale zbyt skomplikowany, aby go wdrożyć, skąd możesz mieć pewność, że algorytm jest poprawny? Bez implementacji nie będzie można przetestować algorytmu w scenariuszu ze świata rzeczywistego, a tak złożony algorytm może zawierać błędy, …
3
Interaktywne dowody za pomocą Postselection?
Zdefiniuj model obliczeniowy MPostBQP, aby był identyczny z PostBQP, z wyjątkiem tego, że dopuszczamy wielomianowo wiele pomiarów kubitowych przed pomiarem selekcyjnym i pomiarem końcowym. Czy możemy podać jakiekolwiek dowody wskazujące, że MPostBQP ma większą moc niż PostBQP? Zdefiniuj MPostBQP [k], aby umożliwić wiele rund pomiaru i wyboru po dokonaniu ostatecznego …
4
Dlaczego automaty z ograniczeniem liniowym nie są tak popularne jak inne automaty?
Z mojego doświadczenia wynika, że ​​języki kontekstowe i automaty z ograniczeniami liniowymi są często pomijane lub przewijane na kursach teorii obliczeń, a nawet są pomijane w niektórych znaczących podręcznikach, chociaż automaty skończone i zmniejszające są bardzo popularne. Z pewnością musi istnieć dobry powód, dla którego LBA są mniej skoncentrowane niż …
2
Informacje o k-SAT (wprowadzenie, ograniczenia, metody itp.)
Chciałbym wiedzieć, gdzie mogę się zwrócić o dobre, delikatne wprowadzenie do k-SAT (może to być dla matematyków, którzy nie mają dobrego przygotowania informatycznego). Chciałbym również znać artykuły, które mogą przeglądać lub wyjaśniać obecne metody rozwiązywania k-SAT. Wreszcie interesują mnie najbardziej znane metody rozwiązywania k-SAT. Chciałbym dowiedzieć się, jaki jest najlepszy …
3
Algorytmy triangulacji wielokąta
Miałem trudności ze znalezieniem algorytmu lub opublikowaniem artykułów na temat triangulacji samoblokującego się wielokąta (również wielokąta o strukturze dziury). Czy ktoś może poprowadzić mnie do znalezienia opublikowanej pracy / algorytmu, proszę? PS: proszę odpowiednio oznaczyć to pytanie, nie mam wystarczającej liczby punktów reputacji, aby to zrobić.
3
Jak mogę losowo wygenerować drzewa o ograniczonej wysokości?
W przypadku projektu, nad którym pracuję, powinienem wygenerować losowo rozciągające się drzewa o ograniczonej wysokości. Zasadniczo wykonuję następujące czynności: 1) Wygeneruj drzewo opinające 2) Sprawdź wykonalność, jeśli to możliwe, zachowaj ją. 1) Zaczynając od minimalnego drzewa opinającego (Prim'a lub Kruskala), dodaję nieistniejącą krawędź i to tworzy cykl, wykrywam ten cykl …
1
Jakieś sformułowania SAT / SMT VRP / VRPTW (TSP, Job-Shop-Scheduling)?
zastanawiam się, czy są jakieś podejścia do formułowania problemu trasy pojazdu z systemem Windows-Time ( VRPTW ) (jako problemem decyzyjnym) jako instancji SAT / SMT? (alternatywnie: TSP) Na przykład: „Czy istnieje prawidłowe rozwiązanie odwiedzające wszystkich klientów w ich ramach czasowych przy n = 10 pojazdach?” Ten problem decyzyjny może być …
2
Permutacje w jedną stronę bez klapy
W skrócie: Zakładając, że istnieją kombinacje jednokierunkowe , czy możemy zbudować taką, która nie ma zapadni? Więcej informacji: Permutacja jednokierunkowa to permutacja którą łatwo obliczyć, ale trudno ją odwrócić ( więcej informacji na temat formalnej definicji znajduje się w wiki tagu jednokierunkowego ). Zazwyczaj rozważamy rodziny permutacji jednokierunkowej, , gdzie …
2
Rozszerzenia twierdzenia Ramseya: monochromatyczne, ale różnorodne
Jako kontynuacja mojego poprzedniego pytania , które rozwiązał Hsien-Chih Chang, oto kolejna próba znalezienia odpowiedniego uogólnienia twierdzenia Ramseya. (Nie musisz czytać poprzedniego pytania; ten post jest samodzielny.) Parametry: podane są liczby całkowite , a następnie jest wybierane jako wystarczająco duże. Terminologia: podzbiór jest podzbiorem rozmiaru .1≪d≪k≪n1≪d≪k≪n1 \ll d \ll k …
1
Twardość NP specjalnego przypadku problemu upakowania ortogonalnego
Pozwolić VVV być zestawem DDD-wymiarowe kształty prostokątne. Dlad∈{1,...,D}d∈{1,...,D}d \in \{1,...,D\} i v∈Vv∈Vv \in V, wd(v)∈Q+wd(v)∈Q+w_d(v) \in \mathbb{Q}^{+} opisuje długość vvv w wymiarze ddd. Ta sama notacja jest używana dla konteneraCCC. TheDDD-wymiarowy problem pakowania ortogonalnego (OPP-DDD) ma zdecydować, czy VVV pasuje do pojemnika CCCbez nakładania się. Formalnie rzecz biorąc, problemem jest …
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.