Pytania otagowane jako co.combinatorics

Pytania dotyczące kombinatoryki i dyskretnych struktur matematycznych

5
Geneza pojęcia treewidth
Moje dzisiejsze pytanie jest (jak zwykle) trochę głupie; ale prosiłbym cię o pomyślne rozważenie. Chciałem wiedzieć o genezie i / lub motywacji leżącej u podstaw koncepcji treewidth. Z pewnością rozumiem, że jest on stosowany w algorytmach FPT, ale nie sądzę, że to był powód, dla którego zdefiniowano to pojęcie. Pisałem …
13
Teoria informacji użyta do udowodnienia trafnych twierdzeń kombinatorycznych?
Jakie są twoje ulubione przykłady, w których teoria informacji jest wykorzystywana do udowodnienia zgrabnego kombinatorycznego stwierdzenia w prosty sposób? Niektóre przykłady, które mogę wymyślić, są związane z dolnymi granicami dla dekodowanych lokalnie kodów, np. W tym artykule: załóżmy, że dla wiązki ciągów binarnych długości ma to, że dla każdego , …
11
Jaki jest najskuteczniejszy sposób generowania losowej permutacji na podstawie probabilistycznych zamian par?
Pytanie, które mnie interesuje, dotyczy generowania przypadkowych permutacji. Biorąc pod uwagę probabilistyczną bramę wymiany par jako podstawowy element konstrukcyjny, jaki jest najbardziej skuteczny sposób na uzyskanie jednolicie losowej permutacji elementów? Tu stosować „probabilistyczny bramy parami wymiany” się operacja, która realizuje brama Przełączanie do wybranych elementów i z pewnym prawdopodobieństwem , …
10
Zastosowania złożoności Kołmogorowa w złożoności obliczeniowej
Nieformalnie mówiąc, złożoność Kołmogorowa ciągu jest długością najkrótszego programu, który wypisuje . Możemy zdefiniować pojęcie „losowego ciągu” używając go ( jest losowy, jeśli ) Łatwo jest zauważyć, że większość ciągów jest losowa (nie ma tak wielu krótkich programów).x x K ( x ) ≥ 0,99 | x |xxxxxxxxxK.( x ) …
12
Zastosowania teorii reprezentacji grupy symetrycznej
Zainspirowany tym pytaniem, a w szczególności ostatnim akapitem odpowiedzi Or, mam następujące pytanie: Czy znasz jakieś zastosowania teorii reprezentacji grupy symetrycznej w TCS? Grupa symetryczna SnSnS_n jest grupą wszystkich permutacji {1,…,n}{1,…,n}\{1, \ldots, n\} o składzie operacji grupowych. Przedstawienie SnSnS_n jest homomorfizmem z SnSnS_n ogólnej grupy liniowego odwracalnych n×nn×nn \times n …
2
Ile różnych kolorów jest potrzebnych, aby ograniczyć możliwości wyboru wykresu?
Wykres jest kkk wyboru (znany również jako kkk -list-colorable ), jeśli dla każdej funkcji fff która odwzorowuje wierzchołki na zestawy kkk kolorów, istnieje przypisanie kolorów ccc tak że dla wszystkich wierzchołków vvv , c(v)∈f(v)c(v)∈f(v)c(v)\in f(v) i takie, że dla wszystkich krawędzi vwvwvw , c(v)≠c(w)c(v)≠c(w)c(v)\ne c(w) . Załóżmy teraz, że wykres …
13
Teoretycznie stosowanie kodów korygujących błędy
Jakie są zastosowania kodów korekcji błędów w teorii oprócz samej korekcji błędów? Jestem świadomy trzech zastosowań: twierdzenia Goldreicha-Levina o twardym rdzeniu, konstrukcji ekstraktora Trevisana i wzmocnienia twardości funkcji boolowskiej (autor: Sudan-Trevisan-Vadhan). Jakie są inne „poważne” lub „rekreacyjne” zastosowania kodów korygujących błędy? UPD: jedna zabawna aplikacja do dekodowania list kodów Reeda-Solomona …
17
Przypuszczenia sugerujące twierdzenie o czterech kolorach
Twierdzenie o czterech kolorach (4CT) stwierdza, że ​​każdy płaski wykres jest czterokolorowy. Istnieją dwa dowody podane przez [Appel, Haken 1976] i [Robertson, Sanders, Seymour, Thomas 1997]. Oba te dowody są wspierane komputerowo i dość przerażające. Istnieje kilka domysłów w teorii grafów, które sugerują 4CT. Rozwiązanie tych przypuszczeń wymaga prawdopodobnie lepszego …
6
Siatka
Aktualizacja : Zestaw przeszkód (tj. „Bariera” NxM pomiędzy rozmiarami siatki do barwienia i bezbarwności) dla wszystkich 4-kolorów bez monochromatycznych prostokątów jest teraz znany . Czy ktoś ma ochotę wypróbować 5 kolorów? ;) Z teorii Ramseya wynika następujące pytanie . Rozważmy -coloring z n -by- m wykres siatki. Występuje, gdy cztery …
2
Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym?
Były dwa pytania zadawane niedawno na cs.se które były albo spokrewnione lub miał szczególny przypadek równoznaczne z następującym pytaniem: Załóżmy, że masz ciąg a1,a2,…ana1,a2,…ana_1, a_2, \ldots a_n z nnn liczb takich, że Rozłóż go na sumę dwóch permutacji, i , z , tak aby∑ni=1ai=n(n+1).∑i=1nai=n(n+1).\sum_{i=1}^n a_i = n(n+1).ππ\piσσ\sigma1…n1…n1 \dots nai=πi+σiai=πi+σia_i = …
2
Metoda wielomianowa dla wyników złożoności
Metody wielomianowe , powiedzmy twierdzenie kombinatoryczne Nullstellensatz i twierdzenie Chevalleya-Ostrzegania, są potężnymi narzędziami w kombinatywnej addytywności. Reprezentując problem z właściwymi wielomianami, mogą zagwarantować istnienie rozwiązania lub liczbę rozwiązań wielomianów. Zostały one wykorzystane do rozwiązania problemów, takich jak ograniczone zestawy sum lub problemy o sumie zerowej , a niektóre twierdzenia w …
8
Jaka jest minimalna liczba bitów wymagana do przechowywania układanki sudoku?
Uwaga: chodzi o standardową łamigłówkę sudoku 9x9. Rozwiązanie musi obsługiwać tylko rozwiązane, legalne zagadki . Dlatego rozwiązanie nie musi obsługiwać pustych komórek i może polegać na właściwościach rozwiązanej łamigłówki sudoku. Zastanawiałem się nad tym, ale nie mogłem wymyślić odpowiedzi, z której byłbym zadowolony. Naiwne rozwiązanie wykorzystywałoby jeden bajt na każdą …
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.