Teoretyczne informatyka

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

2
Maksymalna liczba wewnętrznych ścieżek st nieparzystych wierzchołków
Niech będzie prostym grafem bezkierunkowym i niech będą odrębnymi wierzchołkami. Niech długość prostej ścieżki st będzie liczbą krawędzi na ścieżce. Interesuje mnie obliczenie maksymalnego rozmiaru zestawu prostych ścieżek st, tak że każda ścieżka ma nieparzystą długość, a zestawy wierzchołków każdej pary ścieżek przecinają parami tylko s i t. Innymi słowy, …
2
Funkcja boolowska, która nie jest stała w podprzestrzeniach afinicznych o wystarczająco dużym wymiarze
Interesuje mnie wyraźna funkcja boolowska fa:0 , 1n→0 , 1fa:0,1n→0,1f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}z następującą właściwością: jeśli jest stałe w jakiejś podprzestrzeni afinicznejfafaf , wówczas wymiar tej podprzestrzeni wynosi o ( n ) .0 , 1n0,1n\\{0,1\\}^no ( n )o(n)o(n) Nie jest trudno wykazać, że funkcja symetryczna nie spełnia tej właściwości, …
1
Układanka do cięcia pałeczek
Problem: Dostajemy zestaw drążków o długości całkowitej. Całkowita suma ich długości wynosi n (n + 1) / 2. Czy możemy je rozbić, aby uzyskać kije wielkości czasie wielomianowym? 1 , 2 , … , n1,2),…,n{1,2,\ldots,n} Co zaskakujące, jedynym odniesieniem do tego problemu jest starożytna dyskusja: http://www.iwriteiam.nl/cutsticks.html Co jeszcze wiadomo na …
1
Najbardziej znane wspólne pojemniki dla / przez NP i Parity-P?
Parzystość-P jest zbiorem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może rozróżniać tylko parzystą liczbę lub nieparzystą liczbę ścieżek „akceptacji” (zamiast zerowej lub niezerowej liczby ścieżek akceptacji). Zatem Parity-P jest w zasadzie PP „s karłowate młodsze rodzeństwo: podczas liczy PP czy liczba przyjmujących ścieżkach NP-maszyna jest większość, czy nie ( …
2
Dolne granice złożoności Gaussa
Określić Gaussa złożoność danego matrycy, tak aby minimalna ilość elementarnych wierszy i kolumn operacji wymaganych do matrycy w postaci górnej trójkątnej. Jest to wielkość od do (poprzez eliminację Gaussa). Pojęcie ma sens w każdej dziedzinie.n×nn×nn \times n000n2n2n^2 Ten problem z pewnością wydaje się bardzo podstawowy i musiał zostać zbadany. O …
3
Modele obliczeń ściśle między klasycznym a kwantowym pod względem złożoności zapytań
Powszechnie wiadomo, że komputery kwantowe są silniejsze niż ich klasyczne odpowiedniki pod względem złożoności zapytań . Czy istnieją inne modele (naturalne lub sztuczne), które są ściśle kwantowe i klasyczne pod względem złożoności zapytań? Separacja może być włączona specyficzne problemy: model X oblicza funkcję ze znacznie większą liczbą zapytań niż kwantowe, …
1
Przestrzeń topologiczna związana z SAT: czy jest zwarta?
Spełnialności problemem jest to, oczywiście, podstawowym problemem teoretycznym CS. Bawiłem się jedną wersją problemu z nieskończenie wieloma zmiennymi. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Podstawowe ustawienia. Niech będzie niepustym i prawdopodobnie nieskończonym zestawem zmiennych . Dosłowność to albo zmienna albo jej negacja . Klauzula jest rozróżnieniem skończonej liczby literałów . Na koniec definiujemy formułę …
5
P z wyrocznią z faktoryzacji liczb całkowitych
Właśnie przeczytałem pytanie „ Czy rozkład liczb całkowitych jest problemem NP-zupełnym? ” ... więc postanowiłem poświęcić trochę mojej reputacji :-) zadając kolejne pytanie mając :QQQP(Q is trivial)≈1P(Q is trivial)≈1P(\text{Q is trivial}) \approx 1 Jeśli jest wyrocznią, która rozwiązuje faktoryzacji liczb całkowitych, co jest moc P A ? AAAPAPAP^A Myślę, że …
2
Algorytmy pakowania zestawu
Wydaje się, że w przypadku niektórych problemów NP-trudnych jest dużo pracy nad opracowaniem szybkich algorytmów dokładnych w czasie wykładniczym (tj. Wyniki postaci: Algorytm A rozwiązuje problem w czasie O (c ^ n), przy c małym). Wydaje się, że jest sporo pracy w związku z niektórymi problemami trudnymi dla NP (np. …
1
Agregator blogów TOC jest offline
Przepraszam, jeśli to nie na temat. Wygląda na to, że nazwa domeny wygasła. Mam nadzieję, że niektórzy członkowie społeczności tutaj (nie jestem jednym) mogą wiedzieć, kto był administratorem / właścicielem tej witryny. To był całkiem użyteczny zasób.
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.