Teoretyczne informatyka

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

9
Redukcje z książki.
Jest to zgodne z „ Algorytmami z książki ”. Chociaż redukcje są również algorytmami, pomyślałem, że wątpliwe jest, aby pomyśleć o redukcji w odpowiedzi na pytanie o algorytmy z książki. Stąd osobne zapytanie! Wszelkie redukcje są mile widziane. Zacznę od bardzo prostej redukcji od osłony wierzchołków do multikutów na gwiazdach. …
7
Dlaczego CNF jest używany do SAT, a nie DNF?
Nie do końca rozumiem, dlaczego prawie wszystkie solwery SAT używają CNF zamiast DNF. Wydaje mi się, że rozwiązywanie SAT jest łatwiejsze przy użyciu DNF. W końcu musisz tylko przejrzeć zestaw implantów i sprawdzić, czy jeden z nich nie zawiera zarówno zmiennej, jak i jej negacji. W przypadku CNF nie ma …
6
Analogi wykrywania skompresowanego
x∈Rnx∈Rnx \in \mathbb{R}^nA x A R n R ≪ n A k∥x∥0&lt;k‖x‖0&lt;k\|x\|_0 < kAxAxAxAAARRRnnnR≪nR≪nR \ll nAAAkkk- rzadkie z tak małym jak . Mogę nie mieć najlepiej znanych parametrów, ale to jest ogólny pomysł.R O ( k n o ( 1 ) )xxxRRRO(kno(1))O(kno(1))O(k n^{o(1)}) Moje pytanie brzmi: czy istnieją podobne zjawiska …
3
Uogólniając „sztuczkę środkową” do wyższych wymiarów?
W przypadku algorytmów losowych przyjmujących rzeczywiste wartości „sztuczka medianowa” jest prostym sposobem zmniejszenia prawdopodobieństwa niepowodzenia do dowolnego progu , kosztem tylko wielokrotności narzut. Mianowicie, jeśli wyjście mieści się w „dobrym zakresie” z prawdopodobieństwem (co najmniej) , to uruchamianie niezależnych kopii i przyjmując medianę swoich wyników spowoduje, że wartość spadnie do …
8
Trudne problemy NP na ścieżkach
wszyscy wiedzą, że istnieje wiele problemów decyzyjnych, które są trudne NP na ogólnych wykresach, ale interesują mnie problemy, które są trudne NP, gdy podstawowy wykres jest ścieżką. Czy możesz mi pomóc w zebraniu takich problemów? Znalazłem już powiązane pytanie dotyczące trudnych NP problemów na drzewach .
5
Pisanie pracy jako pojedynczy autor w 1. osobie liczby pojedynczej
Piszę prace z informatyki teoretycznej, będąc czasem nieanonimowym pojedynczym autorem. Wcześniej użyłem liczby pierwszej w liczbie pierwszej w takich dokumentach, np .: Pokażemy, że klasy złożoności X i Y pokrywają się. Nie jestem ani ojczystym językiem angielskim, ani wyjątkowo dobrym językiem angielskim. Niedawno otrzymałem poradę od rodzimego użytkownika języka angielskiego …
1
Złożoność problemu macierzowego
Następujący problem pojawił się ostatnio w moich badaniach. Nie będąc ekspertem od zagadnień algorytmicznych, obszernie poszukiwałem odpowiednich problemów, które można by zmniejszyć. Nie rozumiem, jak działałby 3SAT i chociaż ZOE jest podobny w duchu, redukcja nie jest oczywista. Inną możliwością byłaby egzystencjalna teoria rzeczywistości. To też nie wydaje się pasować, …
4
Problemy, które w praktyce można rozwiązać w sposób sprzeczny z intuicją?
Niedawno przeszedłem przez bolesną zabawę polegającą na nieformalnym wyjaśnianiu koncepcji złożoności obliczeniowej młodemu utalentowanemu samoukiem, programistowi, który nigdy wcześniej nie odbył formalnego kursu algorytmów ani złożoności. Nic dziwnego, że wiele pojęć początkowo wydawało się dziwnych, ale miało sens w niektórych przykładach (PTIME, trudność, niezliczalność) , podczas gdy inne wydają się …
1
Liczba wyraźnych różnic liczb całkowitych wybranych z
Podczas moich badań spotkałem następujący wynik. limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1 gdzie m=ω(n−−√)m=ω(n)m=\omega(\sqrt n) i a1,⋯,ama1,⋯,ama_1,\cdots,a_m są wybierane losowo z [n][n][n] . Szukam referencji / bezpośredniego dowodu. Skrzyżowane na MO
3
Czy wpisane obliczenia lambda wyrażają * wszystkie * algorytmy poniżej określonej złożoności?
Wiem, że złożoność większości odmian kalkulatorów lambda bez prymitywu kombinatora Y jest ograniczona, tzn. Można wyrazić tylko funkcje o ograniczonej złożoności, przy czym granica staje się większa wraz ze wzrostem ekspresyjności systemu typów. Pamiętam, że np. Rachunek konstrukcji może wyrażać co najwyżej podwójnie wykładniczą złożoność. Moje pytanie dotyczy tego, czy …
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.