Teoretyczne informatyka

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

2
Jak trudno policzyć liczbę lokalnych optymów dla problemu w PLS?
W przypadku wielomianowego problemu wyszukiwania lokalnego wiemy, że musi istnieć co najmniej jedno rozwiązanie (lokalne optimum). Jednak może istnieć wiele innych rozwiązań, jak trudno jest policzyć liczbę rozwiązań problemu z kompletnym PLS? Jestem szczególnie zainteresowany w problemu decyzyjnego: nie wystąpienie tego problemu PLS-complete mają dwa lub więcej rozwiązań? Czy złożoność …
1
Ankieta na temat separatorów?
Do tej pory istnieje mnóstwo wyników dotyczących separatorów na wykresach, od płaskiego separatora, separatora drzew, ograniczonych wykresów szerokości drzewa, ograniczonych wykresów rodzajów itp. Itp. Czy jest jakaś dobra zaktualizowana ankieta na ten temat i ich zastosowania?
1
zmaksymalizować MST (G [S]) na wszystkich indukowanych podgraphach G [S] na wykresie metrycznym
Czy ten problem był już badany? Biorąc pod uwagę metryczny niekierowany wykres G (długości krawędzi spełniają nierówność trójkąta), znajdź zestaw S wierzchołków, tak że MST (G [S]) jest zmaksymalizowany, gdzie MST (G [S]) jest minimalnym drzewem rozpinającym podgrafu wywołanym przez S. Czy ten problem był już badany? Czy to trudne …
3
Czy możemy obliczyć
Szukam wydajnego algorytmu dla problemu: Wejście : dodatnia liczba całkowita 3)n3n3^n (zapisana w bitach) dla jakiejś liczby całkowitej n ≥ 0n≥0n \geq 0 . Wyjście : liczba nnn . Pytanie : Czy możemy obliczyć nnn na podstawie bitów 3)n3)n3^n w czasie O ( n )O(n)O(n) ? To jest teoretyczne pytanie …
2
Jaka jest korelacja między wysokością a twardością instancji dla losowego 3-SAT?
Ten ostatni artykuł z FOCS2013, Strong Backdoors to Bounded Treewidth SAT autorstwa Gaspersa i Szeidera mówi o związku między szerokością wykresu klauzuli SAT a twardością instancji. W przypadku losowych instancji 3-SAT, tj. Instancji losowo wybranych 3-SAT, jaka jest korelacja między szerokością wykresu klauzulowego a twardością instancji? „Twardość wystąpienia” może być …
2
Znajdź wszystkie pary wartości bliskich odległości Hamminga
Mam kilka milionów wartości 32-bitowych. Dla każdej wartości chcę znaleźć wszystkie inne wartości w odległości Hamminga wynoszącej 5. W podejściu naiwnym wymaga to porównań O(N2)O(N2)O(N^2) , których chcę uniknąć. Uświadomiłem sobie, że jeśli potraktowałem te 32-bitowe wartości jako liczby całkowite i posortowałem listę raz, to wartości, które różniły się tylko …
2
Różnica między typami i rodzajami
To może być bardzo proste pytanie. Ale jaka jest różnica między rodzajami i rodzajami? Moje obecne rozumienie jest takie, że masz teorię typów z regułami typów, które dają pojęcie dobrze napisanego wyrażenia, ale rodzaje są bardziej podstawowe, różnicując symbole na różne rodzaje symboli i wprowadzając podstawowe zasady dotyczące stosowania funkcji …
2
Klasy wykresów, dla których można obliczyć średnicę w czasie liniowym
Przypomnijmy, średnica grafu oznacza długość najdłuższego najkrótszej ścieżce G . Biorąc pod uwagę wykres, oczywisty algorytm obliczania diam ( G ) rozwiązuje problem wszystkich par najkrótszej ścieżki (APSP) i zwraca długość najdłuższej znalezionej ścieżki.solGGsolGGśrednica ( G )diam(G)\text{diam}(G) Wiadomo, że problem APSP można rozwiązać w optymalnym czasie dla kilku klas grafów. …
2
Wymień wszystkie rozwiązania problemu SAT
Wszystkie znane mi solwery #SAT, np. RelSat, C2D, zwracają tylko liczbę zadowalających wystąpień. Ale chcę poznać każdy z tych przypadków? Czy istnieje taki solver #SAT lub jak powinienem zmodyfikować dostępny solver #SAT, aby to zrobić? Dziękuję Ci.
11 lo.logic  sat  software 
6
Mały język podobny do C, który mogą symulować maszyny Turinga
Szukam małego języka, który pomoże „przekonać” studentów, że maszyny Turinga są wystarczająco ogólnym modelem obliczeniowym. To znaczy język, który wygląda jak języki, do których są przyzwyczajeni, ale można go również łatwo symulować na maszynie Turinga. Papadimitriou używa do tego zadania maszyn RAM, ale obawiam się, że porównanie czegoś dziwnego (jako …
4
Autor zamawia w artykułach TCS
Chociaż ogólna zasada jest taka, że ​​w artykułach TCS autorzy są uporządkowani alfabetycznie, istnieją pewne znaczące kontrprzykłady, które przychodzą na myśl, w których autorzy są uporządkowani w inny sposób, np. Metody algebraiczne dla interaktywnych systemów dowodowych [Lund, Fortnow, Karloff, Nisan] Metoda uzyskiwania podpisów cyfrowych i kryptosystemów klucza publicznego [Rivest, Shamir, …
2
Czy istnieje wytłumaczenie trudności w udowodnieniu kwadratowych dolnych granic dla interesujących problemów NP?
To kontynuacja mojego poprzedniego pytania: Najbardziej znana deterministyczna złożoność czasu dolna granica naturalnego problemu w NP Uważam za zdumiewające, że nie byliśmy w stanie udowodnić żadnego kwadratowego deterministycznego czasu w dolnej granicy jakiegokolwiek interesującego problemu NP, na który ludzie dbają i starają się zaprojektować lepsze algorytmy. Nasza hipoteza o wykładniczym …
2
Determinanty i mnożenie macierzy - podobieństwo i różnice w złożoności algorytmicznej i wielkości obwodu arytmetycznego
Próbuję zrozumieć związek między złożonością algorytmiczną a złożonością obwodów determinant i mnożenia macierzy. Wiadomo, że wyznacznik macierzy można obliczyć w czasie , gdzie to minimalny czas wymagany do pomnożenia dowolnych dwóch macierzy. Wiadomo również, że najlepszą złożonością obwodów wyznaczników jest wielomian na głębokości i wykładniczy na głębokości 3. Ale złożoność …
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.