Teoretyczne informatyka

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

2
Uogólnienie algorytmu minimalizacji DFA Brzozowskiego do automatów skończonych z różnymi klasami stanów akceptujących?
Algorytm Brzozowskiego do przekształcania DFA w równoważny DFA stanu minimalnego jest niezwykle prosty: jeśli oznacza NFA utworzony przez odwrócenie wszystkich krawędzi w DFA , czyniąc stary stan początkowy stanem akceptującym i czyniąc starym akceptowaniem stwierdza początek stanów i jeżeli oznacza wynik zastosowania konstrukcji podzbioru do NFA , a następnie jest …
2
Jaka jest „najmniejsza” klasa złożoności, dla której
Wierzę, że odpowiedzi na to pytanie dają takie klasy, że dla wszystkich wielomianówppp, w klasie występuje problem, który nie ma obwodów wielkościp ( n )p(n)p(n). Pytam jednak o rozmiar obwoduω( n )ω(n)\omega \hspace{.02 in}(n). (⟨00,11,2)2),3)1,44,51,66,71,88,91, . . .⟩(⟨00,11,22,31,44,51,66,71,88,91,...⟩\big(\hspace{-0.07 in}\left\langle \hspace{-0.04 in}0^{\hspace{.02 in}0}\hspace{-0.03 in},\hspace{-0.04 in}1^{\hspace{-0.03 in}1}\hspace{-0.03 in},2^{\hspace{.02 in}2}\hspace{-0.04 in},\hspace{-0.03 in}3^1\hspace{-0.04 in},\hspace{-0.03 …
1
Dlaczego Proof Checker jest wymagany w Proof Carry Code?
W klasycznym dokumencie PLDI'98 autorstwa Neculi „Projekt i implementacja kompilatora certyfikującego” weryfikator wysokiego poziomu wykorzystuje: VCGen generuje warunki weryfikacji (prognozy bezpieczeństwa) Dowódca logiki twierdzenia pierwszego rzędu, aby udowodnić warunki Kontroler sprawdzania LF, aby sprawdzić dowód od kroku (2) Jestem trochę zdezorientowany krokiem (3). Dlaczego w ogóle jest to wymagane? Czy …
1
Czy Stephen Cook dostrzegł znaczenie wykazania, że ​​SAT jest NP-twardy przed faktycznym udowodnieniem?
Jeśli dobrze rozumiem, aby udowodnić, że problem jest trudny NP, musisz wybrać wszystkie możliwe problemy które są w NP, a następnie udowodnić, że redukują się do za pomocą funkcji obliczania czasu wielomianowego, która odwzorowuje wystąpienia każdego z nich do przypadków .ZAAAbjaBiB_{i}ZAAAbjaBiB_{i}ZAAA Po znalezieniu pierwszego trudnego problemu NP, stosując redukcje, możesz …
2
Liczba automorfizmów wykresu dla izomorfizmu grafowego
Niech i będą dwoma połączonymi wykresami regularnymi o rozmiarze . Niech być zbiorem permutacji tak, że . Jeśli następnie jest zestaw automorfizmy o .GGGHHHrrrnnnAAAPPPPGP−1=HPGP−1=HPGP^{-1}=HG=HG=HG=HAAAGGG Jaka jest najbardziej znana górna granica rozmiaru ? Czy są jakieś wyniki dla poszczególnych klas grafów (niezawierających grafów kompletnych / cyklicznych)?AAA Uwaga: Skonstruowanie grupy automorfizmów jest …
1
Czy losowa wyrocznia może zmienić, które problemy TFNP są średnio trudne?
Zastanawiałem się nad następującym pytaniem w różnych momentach, odkąd widziałem to pytanie w kryptografii . Pytanie Pozwolić RRRbyć relacją TFNP . Czy losowa wyrocznia może pomóc P / poli w przełamaniu z nieistotnym prawdopodobieństwem? Bardziej formalnie, RRR \newcommand{\Pr}{\operatorname{Pr}} \newcommand{\E}{\operatorname{\mathbb{E}}} \newcommand{\O}{\mathcal{O}} \newcommand{\Good}{\mathsf{Good}} Robi dla wszystkich algorytmów P / poli , \ …
1
Czy 1-w-3 SAT pozostaje NP-twardy, nawet jeśli każda zmienna występuje zarówno pozytywnie, jak i negatywnie?
Standardowy problem 1-w-3 SAT (lub XSAT lub X3SAT) to: Instancja : formuła CNF z każdą klauzulą ​​zawierającą dokładnie 3 literały Pytanie : czy istnieje zadowalające ustawienie przypisania dokładnie 1 literał na klauzulę prawda? Problem jest NP-zupełny i pozostaje trudny, nawet jeśli żadna zmienna nie zostanie zanegowana. Zastanawiam się, czy problem …
1
Podział krawędzi na tęczowe trójkąty
Zastanawiam się, czy następujący problem jest trudny NP. Wprowadź: prosty wykres i kolorowanie krawędzi ( nie weryfikuje żadnej konkretnej właściwości).G = ( V, E)G=(V,E)G = (V,E)fa: E→ { 1 , 2 , 3 }f:E→{1,2,3}f : E \to \{1,2,3\}faff Pytanie: czy można podzielić na trójkąty , tak aby każdy trójkąt miał …
2
Nazwij klasę wykresów: Rozłączne połączenie kliki i zbioru niezależnego
Pozwolić solsolG być wykresem będącym rozłącznym związkiem kliki i niezależnym zbiorem, tj. G =K.n1+K.n2)¯¯¯¯¯¯¯¯=K.n1+jan2).sol=K.n1+K.n2)¯=K.n1+jan2).G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} . Klasa grafów wszystkich takich wykresów charakteryzuje się zabronionym indukowanym zestawem a zatem jest to przecięcie wykresu skupień i wykresu podziału (lub progu).H ={2K.2),P.3)}H.={2)K.2),P.3)}\mathcal{H} = \{2K_2, P_3\} Czy …
2
Czy istnieje wielowymiarowa gramatyka generatywna?
Interesuje mnie muzyka komputerowa, w której istnieją podejścia do traktowania utworów muzycznych jako zdań w gramatyce generatywnej lub systemach L. Zamiast komponować, można określić gramatykę i pozwolić komputerowi na generowanie muzyki. Np. Grupa Yale wokół zmarłego Paula Hudaka jest w tym bardzo silna. To uderzyło mnie, że używamy reprezentacje pozornie …
9 grammars 
1
Kiedy wykres przyjmuje orientację, w której występuje co najwyżej jeden spacer?
Rozważ następujący problem: Dane wejściowe: prosty (niekierowany) wykres G = ( V, E)sol=(V.,mi)G=(V,E). Pytanie: Czy istnieje orientacja spełniająca właściwość, że dla każdego istnieje co najwyżej jeden (skierowany) - spacer?solsolGs , t ∈ V.s,t∈V.s,t \in Vsssttt Może to być równoważnie sformułowane jako: Dane wejściowe: prosty (niekierowany) wykres .G=(V,E)G=(V,E)G=(V,E) Pytanie: Czy istnieje …
1
Czy znana jest złożoność tego problemu ścieżki?
Instancja: Niekierowany wykresGGGz dwoma wyróżnionymi wierzchołkami i liczbą całkowitą .s≠ts≠ts\neq tk≥0k≥0k\geq 0 Pytanie: Czy istnieje ścieżka w , taka, że ​​przecina ona co najwyżej trójkątów? (W przypadku tego problemu mówi się, że ścieżka przecina trójkąt, jeśli ścieżka zawiera co najmniej jedną krawędź od trójkąta).s−ts−ts-tGGGkkk
1
Czy znana jest złożoność tego problemu?
Niech będzie wykresem. Zestaw wierzchołek nazywa krytyczna jeśli i nie wierzchołek w przylega dokładnie jeden wierzchołek w . Problemem jest znalezienie zbiór wierzchołków z co najmniej taką wielkość, że każdego niezbędny zestaw .G = ( V, E)G=(V,E)G=(V,E)X⊆ V.X⊆VX\subseteq VX≠ ∅X≠∅X\neq\emptysetV.∖ XV∖XV\setminus XXXXS.⊆ V.S⊆VS\subseteq VS.∩ X≠ ∅S∩X≠∅S\cap X\neq\emptysetXXX Problem ma następującą …
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.