Teoretyczne informatyka

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

2
Liczba minut wykresu bez użycia algorytmu Kargera
Wiemy, że algorytm wycinania Kargera można wykorzystać do udowodnienia (w niekonstruktywny sposób), że maksymalna liczba możliwych skrótów może mieć wykres ( n2))(n2))n \choose 2 . Zastanawiałem się, czy moglibyśmy w jakiś sposób udowodnić tę tożsamość, podając bijectywny (raczej iniekcyjny) dowód z zestawu skrótów do innego zestawu liczności ( n2))(n2))n \choose …
1
Czy {ww '| HamDist (w, w ')> 1} bez kontekstu?
Po przeczytaniu ostatniego pytania „Czy uzupełnienie pozbawione kontekstu?” {www∣...}{www∣...}\{ www \mid ...\}; Przypomniałem sobie podobny problem, którego nie byłem w stanie odeprzeć: Czy bez kontekstu?L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|=|w'| \land HamDist(w,w')>1 \} Tutaj wymagamy, aby dwa struny różniły się co najmniej w dwóch pozycjach (odległość …
1
Funkcja, która ma być jednokierunkowa, jeśli istnieją funkcje jednokierunkowe?
Istnieje stara sztuczka polegająca na spisaniu algorytmu, który, jeśli P = NP, rozwiązuje SAT w czasie wielomianowym. Zasadniczo, wymieniono wszystkie wielomianowe wehikuły czasu i wielozadaniowość nad nimi. Czy istnieje analogiczna sztuczka dla funkcji jednokierunkowych (a nawet jednokierunkowych funkcji zapadni)? Czy możemy zapisać funkcję, która, jeśli istnieją funkcje jednokierunkowe, jest koniecznie …
2
Automatyczne uczenie się bez kontrprób
W programie do nauki automatów Angluin , uczeń chce nauczyć się zwykłego języka , zadając swojemu nauczycielowi dwa rodzaje pytań:L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* Zapytania słowne: biorąc pod uwagę , czy ?w∈Σ∗w∈Σ∗w\in \Sigma^*w∈Lw∈Lw\in L Zapytania o równoważność: biorąc pod uwagę język , czy ? Jeśli nie, nauczyciel daje kontrprzykład, to słowo .K⊆Σ∗K⊆Σ∗K\subseteq \Sigma^*K=LK=LK=Lw∈K∖L∪L∖Kw∈K∖L∪L∖Kw\in …
1
Jakie są przeszkody w przedłużeniu
Dowód omer Reingold, że daje algorytm USTCON (W U ndirected wykres ze szczególnym wierzchołki s i t są one Con podłączeń z sieciami?) Za pomocą tylko logspace. Podstawową ideą jest zbudowanie wykresu ekspandera z oryginalnego wykresu, a następnie przejście do wykresu ekspandera. Wykres ekspandera jest tworzony przez wielokrotne kwadratowe obliczenie …
2
Czy algorytm quasiipolomialnego czasu Babai faktycznie generuje izomorfizm?
Mam (mam nadzieję, że proste, może głupie) pytanie na przełomowy artykuł Babai, który pokazuje, że jest quasipolynomial.GIGI\mathsf{GI} Babai pokazał, jak stworzyć certyfikat, że dwa wykresy dla są izomorficzne, z czasem quasipolynomial in.i ∈ { 1 , 2 } v = | V i |Gi=(Vi,Ei)Gi=(Vi,Ei)G_i=(V_i,E_i)i∈{1,2}i∈{1,2}i\in\{1,2\}v=|Vi|v=|Vi|v=|V_i| Czy Babai rzeczywiście pokazać , jak …
1
Wnioski z odwrotnej siły matematycznej twierdzenia graf moll
Załóżmy, że mamy właściwość grafu, którą można sprawdzić w niedeterministycznym czasie wielomianowym, oraz dowód w słabym systemie formalnym (powiedzmy RCA 0 ), że właściwość jest nieznacznie zamknięta. Czy możemy powiedzieć coś o sile systemu formalnego, który jest w stanie udowodnić, że dany skończony zestaw wykluczonych nieletnich charakteryzuje daną właściwość graficzną? …
1
Czy istnieją ciekawe klasy grafów, w których obliczanie szerokości jest trudne (łatwe)?
Treewith jest ważnym parametrem grafu, który wskazuje, jak blisko wykres jest od drzewa (choć nie w ścisłym sensie topologicznym). Powszechnie wiadomo, że obliczenie szerokości jest trudne dla NP. Czy są jakieś naturalne klasy wykresów, w których trudno jest obliczyć szerokość ? Podobnie: Czy istnieją ciekawe klasy grafów, w których obliczanie …
1
Odstęp między
HT(n)HT(n)HT(n)nnnBB(n)=maxHT(n)BB(n)=maxHT(n)BB(n) = \max HT(n) Co możemy powiedzieć o drugiej największej liczbie w ? Nazwij to .HT(n)HT(n)HT(n)BB2(n)BB2(n)BB_2(n) BB2(n)BB2(n)BB_2(n) jest banalnie nieobliczalny, ponieważ pozwala obliczyć : wystarczy poczekać, aż zatrzyma się jeszcze jedna maszyna. Naiwnie oczekiwałbym, że przerwa będzie „zajęta jak bóbr”, rosnąc szybciej niż jakakolwiek funkcja obliczalna. Czy to da się …
1
Parallel Pebble Game on a Line
W grze żwirowej na linii znajdują się N + 1 węzłów oznaczonych od 0 do N. Gra rozpoczyna się od kamyka w węźle 0. Jeśli kamyk znajduje się w węźle i, możesz dodać lub usunąć kamyk z węzła i + 1. Celem jest umieszczenie kamyka na węźle N, bez umieszczania …
1
Twierdzenie Adlemana o nieskończonych półkolach?
Adleman wykazały w 1978 r : Jeżeli logiczna funkcja o zmiennych może być obliczany za pomocą prawdopodobieństwa logicznego obwodu o rozmiarze , a następnie może być obliczany za pomocą deterministycznych obwód boolowski wielomianu wielkości w i ; właściwie o wielkości . BPP⊆P/polyBPP⊆P/poly\mathrm{BPP}\subseteq \mathrm{P/poly}fffnnnMMMfffMMMnnnO(nM)O(nM)O(nM) Pytanie ogólne: W stosunku do innych (boolowskich) …
2
Para cykli rozłącznych wierzchołków na ukierunkowanym wykresie
Jaki jest najszybszy znany algorytm deterministyczny, który może rozpoznawać skierowane wykresy za pomocą pary rozłącznych cykli wierzchołków? Wiem, że wykresy z min. Min. Trzech zawsze mają taką parę ( Thomassen'83 ), ale mimo to nie mogę znaleźć skutecznego algorytmu w ogólnym przypadku. Czy ktoś zna odniesienia do tego?
2
Załamuje się przy założeniu, że
Wiadomo, że w przypadku następnie wielomian hierarchia zapada się Ď P 2 i M A = A M .N.P.⊆ P./ PO l rNP⊆P/PolyNP\subseteq P/PolyΣP.2)Σ2P\Sigma_2^{P}M.= MMA=AMMA = AM Jakie są najsilniejsze znane upadki, jeśli ?N.miXP.⊆ P./ PO l rNEXP⊆P/PolyNEXP\subseteq P/Poly
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.