Мой вопрос сегодня (как обычно) немного глупый; но я бы попросил вас рассмотреть это. Я хотел знать о происхождении и / или мотивации концепции ширины дерева. Я уверен, что понимаю, что это используется в алгоритмах FPT, но я не думаю, что это было причиной, почему это понятие было определено. Я...
Какие ваши любимые примеры, когда теория информации используется, чтобы доказать аккуратное комбинаторное утверждение простым способом? Некоторые примеры, которые я могу придумать, связаны с нижними границами для локально декодируемых кодов, например, в этой статье: предположим, что для двоичных...
Рассмотрим непересекающихся семейств подмножеств {1,2,…, n}, F 1 , F 2 , … F t .TttF1, F2, … FTF1,F2,…Ft{\cal F}_1,{\cal F_2},\dots {\cal F_t} Предположим, что (*) Для каждого , и каждый R ∈ F я и Т ∈ F к , существует S ∈ F J , который содержит R ∩ T .я < J < Ki<j<ki \lt j \lt kR ∈...
Неформально говоря, колмогоровская сложность строки - это длина самой короткой программы, которая выводит . Мы можем определить понятие «случайная строка», используя ее ( является случайным, если ). Легко видеть, что большинство строк случайные (коротких программ не так много).х х К ( х ) ≥ 0,99 |...
Вдохновленный этим вопросом и, в частности, последним абзацем ответа Ор, у меня есть следующий вопрос: Знаете ли вы какие-либо приложения теории представлений симметрической группы в TCS? Симметрическая группа SNSnS_n является группой всех перестановок { 1 , … , n }{1,…,n}\{1, \ldots, n\} с...
Каковы применения кодов, исправляющих ошибки в теории, помимо самого исправления ошибок? Мне известны три приложения: теорема Голдрайха-Левина о жестком ядре, конструкция экстрактора Тревизана и усиление твердости булевой функции (Судан-Тревизан-Вадхан). Каковы другие «серьезные» или...
Граф является выбираемым (также известным как -list-colourable ), если для каждой функции которая отображает вершины в наборы из цветов, существует такое цветовое присвоение , что для всех вершин , , и такие , что для всех ребер Vw , с (v) \ п с (ш) .k f k c v c ( v ) ∈ f ( v ) v w c ( v ) ≠ c ( w...
Теорема о четырех цветах (4CT) гласит, что каждый планарный граф имеет четыре раскраски. Есть два доказательства, представленные [Аппель, Хакен 1976] и [Робертсон, Сандерс, Сеймур, Томас 1997]. Оба эти доказательства являются компьютерными и довольно пугающими. Есть несколько гипотез в теории...
Обновление : теперь известен набор препятствий (то есть «барьер» NxM между размерами окрашиваемой и неокрашиваемой сетки) для всех четырехцветных цветов без монохроматического прямоугольника . Кто-нибудь испытывает желание попробовать 5 цветов? ;) Следующий вопрос возникает из теории Рамсея ....
Были два вопросы недавно спросил о cs.se , которые были либо связанные или имели особый случай , эквивалентный следующему вопросу: Предположим, у вас есть последовательность из n чисел, такая что ∑ n i = 1 a i = n ( n + 1 ) . Разложите его в сумму двух перестановок, π и , из , так что...
Полиномиальные методы , скажем, теорема о комбинаторном нульстелленсаце и Шевалле – Предупреждениее, являются мощными инструментами аддитивной комбинаторики. Представляя проблему с собственными полиномами, они могут гарантировать существование решения или количество решений полиномов. Они...
Я все больше интересуюсь теорией спектральных графов, которая мне кажется интересной, и я начал собирать несколько документов, которые мне еще предстоит прочитать более тщательно, чем то, что я имею до сих пор. Однако мне любопытно высказывание, которое появилось в нескольких источниках (например,...
Примечание: речь идет о стандартной головоломке судоку 9х9. Решение должно поддерживать только разрешенные, легальные загадки . Таким образом, решение не должно поддерживать пустые ячейки и может полагаться на свойства решенной головоломки судоку. Мне было интересно, но я не мог придумать ответ,...
Есть несколько алгоритмов, которые решают за полиномиальное время, можно ли построить график на плоскости или нет, даже многие с линейным временем выполнения. Тем не менее, я не смог найти очень простой алгоритм, который можно было бы легко и быстро объяснить в классе, и показал бы, что PLANARITY в...
В ISGCI списки более 1100 классов графов. Для многих из них мы знаем, можно ли выбрать НЕЗАВИСИМЫЙ НАБОР за полиномиальное время; их иногда называют классами IS-easy . Я хотел бы составить список максимальных классов IS-easy. Эти классы вместе образуют границу (известной) управляемости для этой...
Предположим, что граф с раскрасочным числом . Рассмотрим следующую игру между Алисой и Бобом. В каждом раунде Алиса выбирает вершину, и Боб отвечает цветом для этой вершины. Игра заканчивается, когда монохроматический край обнаружен. Пусть будет максимальной продолжительностью игры при оптимальной...
К моему удивлению, я не смог найти статьи об этом - вероятно, искал не те ключевые слова. Итак, у нас есть массив чего угодно и функция по его индексам; - перестановка.фееfееf Как переупорядочить массив в соответствии с с памятью и временем выполнения, максимально приближенными к и ?O ( 1 ) O ( n...
Я ищу коды с исправлением ошибок следующего типа: двоичные коды с постоянной скоростью, декодируется из некоторой постоянной доли ошибок декодером, реализуемым в виде логической схемы размера , где N - длина кодирования.O(N)O(N)O(N)NNN Немного предыстории: Шпильман, в линейном время кодируемого и...
В моем компьютерном образовании я все чаще замечаю, что большинство дискретных задач являются NP-полными (по крайней мере), тогда как оптимизация непрерывных задач почти всегда легко достижима, обычно с помощью градиентных методов. Есть ли исключения из...
Учитывая регулярный язык (NFA, DFA, грамматика или регулярное выражение), как можно посчитать количество принимаемых слов на данном языке? Интерес представляют как «ровно n букв», так и «не более n букв». У Маргареты Акерман есть две статьи по теме перечисления слов, принятых NFA, но я не смог...