Teoretyczne informatyka

Ostatnio studiuję model obliczeniowy BSS (por. Na przykład złożoność i obliczenia rzeczywiste; Blum, Cucker, Shub, Smale). Na Real , widoczne jest, że biorąc pod uwagę system wielomianu f 1 , ⋯ , f m ∈ R [ x 1 , ⋯ , x n ] Istnienie zer jest N P …

13 cc.complexity-theory  computing-over-reals 

Niech będzie funkcją większościową, tj. F ( x ) = 1 wtedy i tylko wtedy, gdy ∑ n i = 1 x i > n / 2 . Zastanawiałem się, czy istnieje prosty dowód na następujący fakt (przez „prosty” mam na myśli to, że nie polegałem na metodzie probabilistycznej, jak …

13 cc.complexity-theory  circuit-complexity  boolean-functions  circuit-families  circuit-depth 

Ostatnie pytanie (patrz Konsekwencje NP = PSPACE ) dotyczyło „paskudnych” konsekwencji . W odpowiedziach wymieniono kilka skutków zawalenia, w tym i inne, dostarczając wielu powodów, aby wierzyć .N P = c o N P N P ≠ P S P A C EN.P.= PS.P.A C.miNP=PSPACENP=PSPACEN.P.= c o NP.NP=coNPNP=coNPN.P.≠ P.S.P.A C.miNP≠PSPACENP\neq …

13 cc.complexity-theory  complexity-classes  conditional-results 

Dana jest skierowany acykliczny wykres o numer przypisany do każdego wierzchołka ( g : V → N ), i docelową liczbą T ∈ N .G=(V,E)G=(V,E)G=(V,E)g:V→Ng:V→Ng:V\to \mathbb{N}T∈NT∈NT\in \mathbb{N} Problem sumy podzbioru DAG (może występować pod inną nazwą, odniesienie będzie wielki) pyta, czy istnieją wierzchołki , tak że Σ V I g …

13 ds.algorithms  graph-theory  graph-algorithms  approximation-algorithms  subset-sum 

Załóżmy, że istnieje wykres . Chcę sprawdzić, czy można podzielić na dwa rozłączne zestawy i tak, że podgrupy indukowane przez i są wykresami interwałów jednostkowych.G=(V,E)G=(V,E)G=(V,E)VVVV1V1V_1V2V2V_2V1V1V_1V2V2V_2 Wiem o kompletności NP określania liczb przedziałów, ale powyższy problem jest inny. Teraz w literaturze znalazłem tę pracę A. Gyárfás i D. Westa na wykresach …

13 graph-theory  partition-problem  interval-graphs 

Załóżmy, że spotykasz się z programistami, którzy odbyli profesjonalne kursy programowania (/ self-think), ale nie studiowali matematyki na poziomie uniwersyteckim. Aby pokazać im piękno TCS, chciałbym zebrać kilka fajnych wyników / otwartych pytań pochodzących z TCS, które można łatwo wyjaśnić. Dobry kandydat do tego celu (IMHO) pokaże, że problem zatrzymania …

13 soft-question  big-list  big-picture  teaching 

Czy następujące elementy mogą być przechowywane jednocześnie? jest zawarte w L s + 1 dla wszystkich dodatnich liczb całkowitych s .L.sLsL_sL.s + 1Ls+1L_{s+1}sss jest język wszystkich ograniczonych słów nad { 0 , 1 } .L = ⋃sL.sL=⋃sLsL = \bigcup_s L_s{ 0 , 1 }{0,1}\{0,1\} Istnieje pewna klasa złożoności i pojęcie …

13 cc.complexity-theory  complexity-classes  reductions 

W Bundeswettberweb Infomatik 2010/2011 pojawił się interesujący problem: Dla stałej znajdź minimalne i mapę , tak że nie ma potrójnego z .nnnkkkφ:{(i,j)|i≤j≤n}→{1,…,k}φ:{(i,j)|i≤j≤n}→{1,…,k}\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow \{1,\ldots,k\}(i,j),(i+l,j),(i+l,j+l)(i,j),(i+l,j),(i+l,j+l)(i,j),(i+l,j),(i+l,j+l)φ(i,j)=φ(i+l,j)=φ(i+l,j+l)φ(i,j)=φ(i+l,j)=φ(i+l,j+l)\varphi(i,j)=\varphi(i+l,j)=\varphi(i+l,j+l) Mianowicie szukamy minimalnej ilości kolorów dla trójkąta, tak aby nie było równomiernego podtekstu równobocznego (poniższy rysunek pokazuje nieprawidłowe zabarwienie, ponieważ podświetlone wierzchołki tworzą …

13 graph-theory  sat  combinatorics 

Czym dokładnie jest informatyka teoretyczna? Czy uczy się kodować w różnych językach i tworzy aplikacje na platformach? A może myślisz o coraz szybszych algorytmach, aby komputery mogły efektywniej wykonywać zadania? A może programowanie i myślenie o nowych sytuacjach życiowych, które można symulować na komputerze? Co dokładnie staramy się tutaj zrobić? …

13 big-picture 

Jakiś czas temu wysłałem prośbę o referencję dotyczącą problemów z grafem, w której chcemy znaleźć 2-partycję krawędzi, w której oba zestawy spełniają właściwość niezwiązaną z ich licznością. Próbowałem udowodnić, że następujący problem jest NP-trudny: Biorąc pod uwagę turniej , czy istnieje zestaw sprzężeń zwrotnych F ⊆ E w G, który …

13 np-hardness  reductions 

Rozważ następujący problem. Dane wejściowe: niekierowany wykres . Dane wyjściowe: wykres H, który jest niewielką wartością G, o najwyższej gęstości krawędzi wśród wszystkich nieletnich G , tj. O najwyższym stosunku | E ( H ) | / | V ( H ) | .G=(V,E)G=(V,E)G=(V,E)HHHGGGGGG|E(H)|/|V(H)||E(H)|/|V(H)||E(H)|/|V(H)| Czy zbadano ten problem? Czy jest …

13 graph-theory  graph-algorithms  np-hardness  graph-minor 

W związku z tym pytaniem przyszło mi do głowy: jaka jest złożoność czasu w przypadku maszyny Turinga z pojedynczą taśmą do obliczenia długości danych wejściowych? Mówiąc ściślej, powiedzmy, że alfabet na taśmie to , wejściem jest ciąg znaków w ( 0 + 1 ) ∗ otoczony spacjami, maszyna zaczyna się …

13 turing-machines 

Przypomnijmy transformację przechodzącą kontynuację (transformacja CPS), która przyjmuje do β A : = R R A (gdzie R jest ustalone) if : A → B do β f : β A → β B zdefiniowane przez βZAAAβOdp . : = RRZAβA:=RRA\beta A \mathrel{{:}{=}} R^{R^A}RRRfa: A → Bf:A→Bf : A \to …

13 functional-programming  monad  continuations  cps-transforms 

Nieformalnie funkcje jednokierunkowe są definiowane w odniesieniu do algorytmów PTIME. Są obliczalne w czasie wielomianowym, ale nie są odwracalne w czasie wielomianowym średniego przypadku. Istnienie takich funkcji jest ważnym otwartym problemem w informatyce teoretycznej. Interesują mnie funkcje jednokierunkowe (niekoniecznie dla aplikacji kryptograficznych) zdefiniowane w odniesieniu do różnych granic zasobów. Takimi …

13 cc.complexity-theory  one-way-function 

Niech będzie funkcją boolowską zmiennych boolowskich. Niech będzie oczekiwaną wartością gdy jest uzyskane z poprzez odwrócenie każdej współrzędnej z prawdopodobieństwem .n g ( x ) = T ϵ ( f ) ( x ) f ( y ) y x ϵ / 2faffnnnsol( x ) = Tϵ( f) ( x …

13 cc.complexity-theory  circuit-complexity  boolean-functions