Teoretyczne informatyka

2

Automaty skończone, które akceptują ciągi binarne podzielne przez n

Pracuję nad zestawem problemów dla klasy i pomyślałem o pytaniu związanym z tym, nad czym pracowałem. Czy istnieje minimalna liczba stanów, które musi mieć automat skończony, aby zaakceptować ciągi binarne reprezentujące liczby podzielne przez liczbę całkowitą n? We wcześniejszym zestawie problemów udało mi się zbudować DFA, który akceptuje łańcuchy binarne …

18 automata-theory

3

Determinant modulo m

Jakie są znane skuteczne algorytmy do obliczania wyznacznikiem macierzy współczynników całkowitą o ZmZm\mathbb{Z}_m , pierścień reszt modulo mmm . Liczba mmm może nie być liczbą pierwszą, lecz złożoną (więc obliczenia są wykonywane w pierścieniu, a nie w polu). O ile mi wiadomo (czytaj poniżej), większość algorytmów jest modyfikacjami eliminacji Gaussa. …

18 ds.algorithms reference-request linear-algebra comp-number-theory

11

Czy są jakieś zastosowania technik analizy rzeczywistej w informatyce teoretycznej?

Rozglądałem się daleko za takimi aplikacjami i najczęściej okazało się, że są krótkie. Potrafię znaleźć wiele zastosowań topologii i podobnych struktur na zestawach policzalnych (lub niepoliczalnych), ale rzadko znajduję zbiory niepoliczalne jako przedmiot badań przez informatyków, a zatem prowadzi to do potrzeby technik analizy.

18 co.combinatorics big-picture

3

Najkrótsza równoważna formuła CNF

Niech będzie zadowalającą formułą CNF z zmiennymi i klauzulami . Niech będzie przestrzenią rozwiązań .F1F1F_1m S F 1 F 1nnnmmmSF1SF1S_{F_1}F1F1F_1 Rozważ problem z określeniem, biorąc pod uwagę , innej formuły CNF z tym samym zestawem zmiennych co , z (ta sama przestrzeń rozwiązania co ), ale z możliwie jak najmniejszą …

18 cc.complexity-theory co.combinatorics sat formulas

4

Lista twierdzeń stwierdzających, że P nie jest równe NP wtedy i tylko wtedy, gdy

Myślę, że dobrym pomysłem byłoby sporządzenie listy twierdzeń stwierdzających, że P nie jest równe NP wtedy i tylko wtedy, gdy takie i takie wyjścia, pewna klasa złożoności jest zawarta w innej klasie złożoności i tak dalej.

18 cc.complexity-theory big-list p-vs-np

3

Dokładne rozwiązywanie superstrun

Co wiadomo o dokładnej złożoności najkrótszego problemu superstrun? Czy można to rozwiązać szybciej niż O∗(2n)O∗(2n)O^*(2^n) ? Czy znane są algorytmy, które rozwiązują najkrótszy superstrun bez redukcji do TSP? UPD: O∗(⋅)O∗(⋅)O^*(\cdot) tłumi czynniki wielomianowe. Najkrótszy problem superstrun to problem, którego odpowiedzią jest najkrótszy ciąg, który zawiera każdy ciąg z danego zestawu …

18 cc.complexity-theory ds.algorithms graph-theory tsp exp-time-algorithms

3

Dlaczego umarły badania nad hiper-obliczeniami?

W latach 90. widzę wiele badań nad hiper-obliczeniami , ale w ostatnich latach wydaje się, że niewiele jest pracy na ten temat. Czy to prawda, że badania w tej dziedzinie wygasły? Jeśli tak, jakie mogą być tego przyczyny? Czy ten obszar przekonująco okazał się mało obiecujący?

18 reference-request computability hypercomputation

6

Algorytmy SAT nie oparte na DPLL

Czy są jakieś algorytmy rozwiązywania SAT, które nie są oparte na DPLL? Czy wszystkie algorytmy używane przez solwery SAT są oparte na DPLL?

18 ds.algorithms reference-request sat

4

Zautomatyzowane twierdzenie dowodzące w logice liniowej

Czy automatyczne dowodzenie twierdzeń i przeszukiwanie dowodów jest łatwiejsze w liniowych i innych zdaniach logiki strukturalnej pozbawionej kurczenia? Gdzie mogę przeczytać więcej o automatycznym dowodzeniu twierdzeń w tych logikach i roli skurczu w poszukiwaniu dowodów?

18 reference-request lo.logic survey automated-theorem-proving linear-logic

2

Zastosowania XORification

XORification to technika utrudniania funkcji lub formuły boolowskiej poprzez zastąpienie każdej zmiennej XOR k ≥ 2 odrębnych zmiennych x 1 ⊕ … ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Zdaję sobie sprawę z zastosowania tej techniki w złożoności dowodu, głównie w celu uzyskania niższych granic przestrzeni dla …

18 cc.complexity-theory reference-request boolean-functions proof-complexity

1

Jakie jest najlepsze przybliżenie dla większości głosów?

Większość operacji głosowania pojawia się dość często w tolerancji na uszkodzenia (i bez wątpienia w innych miejscach), gdzie funkcja generuje bit równy, która zawsze pojawia się najczęściej w wartości bitów wejściowych. Dla uproszczenia załóżmy, że ilekroć wejście zawiera taką samą liczbę bitów w stanie 0 i stanie 1, wyprowadza 0. …

18 co.combinatorics

3

Analiza CFG przy użyciu spacji

Istnieje wiele algorytmów, które mogą analizować gramatykę bezkontekstową w czasie . Używając mnożenia macierzy, można nawet iść asymptotycznie szybciej.O(n3)O(n3)O(n^3) Jednak wszystkie algorytmy do analizy dowolnych CFG, które znam, mają najgorsze wykorzystanie przestrzeni (chociaż, co prawda, nie mam pojęcia, jakie jest użycie przestrzeni przez ten algorytm mnożenia macierzy). Zastanawiałem się, czy …

18 ds.algorithms fl.formal-languages space-bounded parsing context-free

2

Tymczasowo płaskie jednokierunkowe obliczenia kwantowe

Na sercu jestem fizykiem, więc myślę, że One-Way Quantum Computing jest genialny. W szczególności obliczenia kwantowe oparte na pomiarach stanu graficznego (MBQC) stanowiły bardzo udany rozwój badań nad obliczeniami kwantowymi, których autorami są Raussendorf & Briegel . Trzeba tylko przygotować stan splątania wieloczęściowego zgodnie z opisem na wykresie, a następnie …

18 quantum-computing

2

Obliczenia poza jednostkowymi macierzami

Z ciekawości, jeśli klasyczne obliczenia dotyczą matryc permutacyjnych, a obliczenia kwantowe dotyczą macierzy jednostkowych (których macierze permutacyjne stanowią podgrupę), to czy będzie jakiś paradygmat obliczeniowy poza macierzami jednolitymi?

18 quantum-computing philosophy

2

Złożoność obliczania dyskretnej transformaty Fouriera?

Jaka jest złożoność (na standardowej całkowitej liczbie pamięci RAM) obliczania standardowej dyskretnej transformaty Fouriera wektora nnn liczb całkowitych? Klasyczny algorytm szybkich transformacji Fouriera , niewłaściwie [1] przypisany Cooleyowi i Tukeyowi, jest zwykle opisywany jako działający w czasie O ( n logn )O(nlog⁡n)O(n \log n) . Ale większość operacji arytmetycznych wykonywanych …

18 ds.algorithms time-complexity computing-over-reals computable-analysis