Teoretyczne informatyka

3

Jakie ograniczenia można nałożyć na liczenie osiągalnych węzłów w dag?

Podany jest sztylet. Chcesz oznaczyć każdy węzeł liczbą dostępnych węzłów. jest trywialną górną granicą; Ω ( V + E ) to dolna granica (tak myślę). Czy istnieje lepszy algorytm? Czy istnieje powód, by sądzić, że dolną granicę można poprawić (powiązane: co dokładnie wiadomo o dolnych granicach w przypadku przechodzenia przejściowego)?O …

23 ds.algorithms graph-theory

16

Jakich narzędzi używasz do prezentacji?

Zastanawiałem się, jakich narzędzi używają ludzie z tej dziedziny (teoretyczna informatyka) do tworzenia prezentacji. Ponieważ duża część informatyki to nie tylko pisanie artykułów, ale także wygłaszanie prezentacji, pomyślałem, że będzie to ważne miękkie pytanie. Jest to inspirowane poprzednim pytaniem, jakich narzędzi używasz do pisania prac . Najczęstsze, które widziałem, są …

23 soft-question research-practice writing

1

Czy

W ankiecie „Małe głębokości obwodów kwantowych” D. Bery, F. Greena i S. Homera (s. 36 z ACM SIGACT News, czerwiec 2007 t. 38, nr 2) przeczytałem następujące zdanie: Klasyczna wersja (w której bramki i mają co najwyżej stały wentylator) jest wyraźnie słabsza niż .QAC0QAC0QAC^0ANDANDANDORORORAC0AC0AC^0 Brak odniesienia do tego roszczenia. Nazwę …

23 cc.complexity-theory circuit-complexity

3

Wykres Izomorfizm i ukryte podgrupy

Próbuję zrozumieć związek między izomorfizmem grafu a problemem ukrytej podgrupy. Czy jest na to dobre odniesienie?

23 cc.complexity-theory reference-request quantum-computing graph-isomorphism

1

Cliquewidth of Almost Cographs

( Wysłałem to pytanie do MathOverflow dwa tygodnie temu, ale jak dotąd bez ścisłej odpowiedzi) Mam pytanie dotyczące miar szerokości wykresu niekierowanych prostych wykresów. Powszechnie wiadomo, że wykresy (wykresy, które można budować za pomocą operacji rozłącznego łączenia i uzupełniania, poczynając od izolowanych wierzchołków) mają najwyżej 2-krotność (Courcelle i in., Górne …

23 graph-theory co.combinatorics cliquewidth

3

Co wiadomo na temat rozwiązań rzadkich problemów z programowaniem liniowym?

Jeśli mam zestaw ograniczeń liniowych, w których każde ograniczenie ma co najwyżej (powiedzmy) 4 zmienne (wszystkie nieujemne i o współczynnikach {0,1}, z wyjątkiem jednej zmiennej, która może mieć współczynnik -1), co wiadomo o rozwiązaniu przestrzeń? Nie interesuje mnie wydajne rozwiązanie (choć proszę wskazać, czy jedno jest znane) niż wiedza o …

23 co.combinatorics integer-programming

6

Rodziny wykresów z wielomianowymi algorytmami czasowymi do obliczania liczby chromatycznej

Post zaktualizowany 31 sierpnia : dodałem podsumowanie aktualnych odpowiedzi poniżej oryginalnego pytania. Dzięki za wszystkie interesujące odpowiedzi! Oczywiście każdy może nadal publikować wszelkie nowe ustalenia. Dla których rodzin grafów istnieje algorytm wielomianowy do obliczania liczby chromatycznej ?χ(G)χ(G)\chi(G) Problem można rozwiązać w czasie wielomianowym, gdy (wykresy dwudzielne). Na ogół, gdy χ …

23 ds.algorithms graph-theory co.combinatorics

1

Jaki jest status wyniku izomorfizmu grafu Babai?

Minęło ponad rok od wycofania i korekty w styczniu 2017 r. Czy są jakieś wiadomości? Jeśli nie, czy to normalne, że walidacja trwa tak długo? Spodziewałbym się, że zyska dużo uwagi. Czy ktoś z ważnych osób wypowiedział się, by poprzeć / wątpić w quasi-wielomianowy wynik?

23 cc.complexity-theory graph-isomorphism proofs

4

Jakie są dowody, że Izomorfizm Grafów nie występuje w

Motywowane komentarzu Fortnow w sprawie mojego postu, dowód, że problemem nie jest izomorfizm grafów -CompleteNPNPNP G I N P N P P G I P , a fakt, że jest głównym kandydatem do -intermediate problemu (nie -Complete ani w ) Jestem zainteresowany znanych dowodów że nie jest w .GIGIGINPNPNPNPNPNPPPPGIGIGIPPP Jednym …

23 cc.complexity-theory graph-isomorphism

2

Testowanie, czy litery można zaplanować, aby uzyskać słowo w zwykłym języku

I ustalić język regularny na alfabetem , i rozważmy następujący problem, który ja nazywam się harmonogram dla . Nieoficjalnie, dane wejściowe dają mi liter i odstępy dla każdej litery (tj. Minimalną i maksymalną pozycję), a moim celem jest umieszczenie każdej litery w tym przedziale, tak aby żadne dwie litery nie …

23 cc.complexity-theory np-hardness automata-theory regular-language scheduling

1

Dla którego k jest PLANAR NAE k-SAT w P?

Problem nie wszystkie równe SAT (NAE -SAT), biorąc pod uwagę zbiór klauzul nad zestawem zmiennych boolowskich, tak że każda klauzula zawiera co najwyżej literałów, pyta, czy istnieje przyporządkowanie zmiennych do takich wartości, że każda klauzula zawiera co najmniej jeden prawdziwy i co najmniej jeden fałszywy literał.k C X kkkkkkkdoCCXXXkkk Problem …

23 cc.complexity-theory reference-request np-hardness polynomial-time

4

Jak sprawdzić, czy liczba jest idealną potęgą w czasie wielomianowym

Pierwszym krokiem algorytmu testowania pierwotności AKS jest sprawdzenie, czy liczba wejściowa jest mocą doskonałą. Wydaje się, że jest to dobrze znany fakt w teorii liczb, ponieważ artykuł nie wyjaśnił go szczegółowo. Czy ktoś może mi powiedzieć, jak to zrobić w czasie wielomianowym? Dzięki.

23 ds.algorithms nt.number-theory

2

Jakie mamy dowody na (i przeciw) hipotezę o unikalnych grach?

Subhash KHOT „s Unikalne Gry Conjecture jest jednym z aktywnych obszarów badawczych w teorii złożoności. Jakie mamy na to dowody? Jakie mamy na to dowody?

23 cc.complexity-theory unique-games-conjecture

2

Czy łańcuchy zmiany biegów są dwukolorowe?

Dla A ⊂ [ n ]A⊂[n]A\subset [n] Oznaczmy przez zajaaia_ijat godzithi^{th} najmniejszy element ZAAA . Na dwa kkk -elementowe zestawów, A , B ⊂ [ n ]A,B⊂[n]A,B\subset [n] , mówimy, że ≤ B jeśli ja ≤ b I dla każdego I .A ≤ BA≤BA\le Bzaja≤ bjaai≤bia_i\le b_ijaii kkk -uniform hipergraf …

23 co.combinatorics graph-colouring hypergraphs

2

Czy są jakieś trudne przypadki 3-SAT, gdy klauzule mogą używać tylko literałów, które są „w pobliżu”?

Niech zmiennymi będą . Odległość między dwiema zmiennymi jest zdefiniowana jako. Odległość między dwoma literałami jest odległością między odpowiednimi dwiema zmiennymi. d ( x a , x b ) = | a - b |x1, x2), x3). . . xnx1,x2,x3...xnx_1 , x_2 , x_3 ... x_nre( xza, xb) = | …

22 np-hardness sat