Teoretyczne informatyka

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

2
Lista problemów trudnych dla NP, w których prowadzone są aktywne badania w zakresie praktycznej heurystyki
Szukam listy problemów związanych z optymalizacją trudnych NP, gdzie są aktywne badania w praktycznej heurystyce w celu ich rozwiązania i istnieją wspólne testy porównawcze, które ludzie próbują pokonać. Przykłady obejmują: rekonstrukcja drzewa filogenetycznego (heurystyczny na przykład tutaj ) komiwojażera (nie tak aktywny, ale LKH jest dość dobrze znana) Mówiąc dokładniej, …
2
Czy istnieje problem obliczeniowy, który występuje w quasi-wielomianowym czasie, ale (być może) go nie ma
Czas quasi-wielomianowy, w skrócie QP, jest klasą złożoności na deterministycznej maszynie Turinga. Oto dokładna definicja: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp Podczas gdy βP jest klasą złożoności o ograniczonym niedeterminizmie. Oto dokładna definicja: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap Łatwo zauważyć, że dowolna maszyna βP może być symulowana przez maszynę QP, a mianowicie βP ⊆⊆\subseteq QP. Ale czy mamy przykład …
1
Jednolita derandomizacja klas złożoności obwodów
Pozwolić CC\mathcal{C} być klasą złożoności i BP-CBP-C\textrm{BP-}\mathcal{C} być randomizowanym odpowiednikiem CC\mathcal{C} zdefiniowane w taki sam sposób jak BPPBPP\textrm{BPP} jest zdefiniowany w odniesieniu do PP\textrm{P}. Bardziej formalnie zapewniamy wielomianowo wiele losowych bitów i akceptujemy dane wejściowe, jeśli prawdopodobieństwo, że zostanie zaakceptowane, jest zakończone2323\frac{2}{3}. W poprzednim poście zapytałem, czy wiadomo, czy równość …
1
Przejście do członkostwa monoidów w DFA
Biorąc pod uwagę pełne DFA A=(Q,Γ,δ,F)A=(Q,Γ,δ,F)A=(Q, \Gamma, \delta, F), możemy zdefiniować zbiór funkcji fafaf_a dla każdego a∈Γa∈Γa\in \Gammai z fa:Q→Qfa:Q→Qf_a:Q\rightarrow Q, fa(q)=δ(q,a)fa(q)=δ(q,a)f_a(q)=\delta(q, a). Możemy uogólnić to pojęcie na słowow=a1,⋯,amw=a1,⋯,amw=a_1, \cdots, a_m i fw=fa1∘⋯∘famfw=fa1∘⋯∘famf_w=f_{a_1}\circ \cdots \circ f_{a_m} gdzie ∘∘\circoznacza skład funkcji. Ponadto oznaczamyG={fw∣w∈Γ∗}G={fw∣w∈Γ∗}G=\{f_w\mid w\in \Gamma^*\} i GGG jest monoidem. [GGGjest zwykle …
1
Rozpoznawanie automatów
Pozwolić ΣΣ\Sigmabyć skończonym alfabetem. kod XXX nad ΣΣ\Sigma jest podzbiorem Σ∗Σ∗\Sigma^* tak, że każde słowo w X∗X∗X^* może być jednoznacznie przedstawiony jako połączenie słów w XXX. KodXXXjest skończony, jeśli| X||X||X|jest skończony. Co wiadomo na temat (minimalnego) rozpoznawania automatówX∗X∗X^*dla skończonego kodu ? Czy istnieje jakaś charakterystyka takich automatów (pod względem budowy …
1
Lemat normalizacyjny Noether dla pól skończonych
Moje pytanie dotyczy twierdzeń 4.1 i 4.2 w „Teorii złożoności geometrycznej V” . Pierwsze twierdzenie mówi, że istnieje algorytm EXPSPACE do konstruowania hsop dlaΔ [ det , m ]Δ[det,m]\Delta[\text{det},m] (patrz definicje w artykule) na doC\mathbb{C} (w rzeczywistości na dowolnym algebraicznie zamkniętym polu o charakterystycznym zeru). Drugi zawiera probabilistyczny wielościeżkowy algorytm …
9 gct 
3
Klasa języków rozpoznawalna przez 3-stanowe TM z pojedynczą taśmą
Przez pewien czas byłem ciekawy maszyn Turinga z dokładnie jedną taśmą i dokładnie 3 stanami (mianowicie stanem początkowym q0q0q_0, stan akceptacji i stan odrzucenia ). Zauważ, że zezwalam na dowolne (skończone) alfabety taśmowe (tzn. Alfabet na taśmie nie jest ograniczony do równego alfabetowi wejściowemu).qacceptqacceptq_{accept}qrejectqrejectq_{reject} Dla wygody zadzwoń do klasy języków …
2
Liczba minimalnych DFA wielkości co najwyżej ?
Niech będzie alfabetem wielkości i rozważmy minimalne DFA, których rozmiar jest ograniczony co najwyżej . Niech oznacza liczbę różnych takich minimalnych DFA.ΣΣ\Sigma222mmmf(m)f(m)f(m) Czy możemy znaleźć formułę zamkniętą dla ?f(m)f(m)f(m) Biorąc pod uwagę, że dla funkcją przejścia DFA o wielkości co najwyżej jest wykres. Ponieważ stopień węzłów jest ograniczony przez , …
1
Zwykłe języki i stała złożoność komunikacji
Pozwolić L⊆A∗L⊆A∗L \subseteq A^* być językiem i zdefiniować fL:A∗×A∗→{0,1}fL:A∗×A∗→{0,1}f_L\colon A^* \times A^* \to \{0, 1\} przez fL(x,y)=1fL(x,y)=1f_L(x, y) = 1 iff x⋅y∈Lx⋅y∈Lx\cdot y \in L. Szukam referencji dla: Propozycja. LLL jest regularna w deterministycznej złożoności komunikacji fLfLf_L jest stały. Innymi słowy, LLL jest normalny iff istnieje protokół dla dwóch graczy …
1
2-NEXPTIME-zupełne problemy
Mamy problem i znaleźliśmy algorytm, który wydaje się być 2-sekundowy. Chciałbym znaleźć znane problemy z niepełnym czasem 2, aby znaleźć dolną granicę. W literaturze znalazłem głównie dwa takie problemy: czy PCP jako rozwiązanie o rozmiarze mniejszym niż 2)2)n2)2)n2^{2^n} i problem uprawy roli dla kwadratu wielkości 2)2)n2)2)n2^{2^n} Jednak nie byłem w …
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.