Этот вопрос похож на один из моих предыдущих вопросов. Известно, что является запрещенным минором для графов с шириной не более t .Kt+2Kt+2K_{t+2}ttt Существует ли красиво построенное, параметризованное, бесконечное семейство графов (кроме полных графов и сеточных графов), которые являются...
Учитывая , сколько из -DNF с переменными и предложениями являются тавтологическими? (или сколько CNF неудовлетворительно?)к н м кm,n,km,n,km, n,
Сетевой коммутатор (название придумано) выполнен с тремя типами узлов: один начальный узел один конечный узел один или несколько узлов коммутатора Узел коммутатора имеет 3 выхода: влево, вверх, вправо; имеет два состояния L и R и целевое состояние TL или TR . Каждый переключатель может быть пройден...
Будем говорить , что граф является ( , б ) связным , если удаление любых через вершины и любые б ребер из G листьев всегда связного графа. Например, k- связный граф, согласно стандартному определению, ( k - 1 , 0 ) -связный, согласно новому определению. Существует ли алгоритм полиномиальное время ,...
Контекст: отношения между логикой и автоматами Теорема Бучи гласит, что монадическая логика второго порядка над строками (MSO) охватывает класс регулярных языков. Фактически доказательство показывает, что экзистенциальный MSO ( или EMSO ) над строками достаточен для захвата обычных языков. Это...
Давайте предположим, что мы создали универсальный квантовый компьютер. За исключением вопросов, связанных с безопасностью (криптография, конфиденциальность, ...), какие текущие проблемы реального мира могут извлечь выгоду из его использования? Я заинтересован в обоих: проблемы, в настоящее время...
Я ищу алгоритм для объединения двух двоичных деревьев поиска произвольного размера и диапазона. Очевидный способ , которым я бы идти о реализации этого было бы найти целые поддерева чьих диапазона может поместиться в произвольный внешний узел в другом дереве. Однако наихудшее время выполнения для...
Много лет назад я слышал, что вычисление минимального NFA (недетерминированного конечного автомата) из DFA (детерминированного) было открытым вопросом, в отличие от обратного направления, которое было известно в течение десятилетий и хорошо исследовано с эффективным алгоритм. Кто-нибудь придумал...
(также спрашивается здесь , без ответов) -квантовый расширитель является распределение над унитарной группой со свойством , что: а) , b) , где \ mu_H - мера Хаара. Если вместо распределений по унитарным мы рассмотрим распределения по матрицам перестановок, нетрудно увидеть, что мы восстанавливаем...
Фрактальный лабиринт - это лабиринт, который содержит копии самого себя. Например, следующий от Mark JP Wolf из этой статьи : Начните с МИНУС и пройдите в ПЛЮС. Когда вы вводите уменьшенную копию лабиринта, обязательно запишите название буквы этой копии, так как вам придется оставить эту копию на...
Ограниченные во времени квантовые вычисления, очевидно, очень интересны. Как насчет квантовых вычислений, ограниченных пространством? Я знаю много интересных результатов для квантовых вычислений с сублогарифмическими пространственными границами и различными типами моделей квантовых автоматов. С...
Насколько мне известно, большинство реализаций генерации псевдослучайных чисел на практике используют такие методы, как регистры обратной связи с линейным сдвигом (LSFR) или эти алгоритмы "Mersenne Twister". Хотя они проходят множество (эвристических) статистических тестов, нет никаких...
2dca (двусторонние детерминированные автоматы с одним счетчиком) (Petersen, 1994) могут распознавать следующий унарный язык: POWER={02n∣n≥0}.POWER={02n∣n≥0}.\begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{equation} Есть ли другой нетривиальный унарный язык,...
Я читал о классах графов , для которых Изоморфизм графов ( ) находится в P . Одним из таких случаев являются графы ограниченной валентности (максимально над степенью каждой вершины), как описано здесь . Но я нашел это слишком абстрактным. Я был бы благодарен, если бы кто-нибудь мог предложить мне...
Планарные графы имеют род ноль. Графы, встраиваемые в тор, имеют род не более 1. Мой вопрос прост: Есть ли какие-нибудь проблемы, которые полиномиально разрешимы на плоских графах, но NP-трудны на графах рода один? В более общем смысле, существуют ли проблемы, которые полиномиально разрешимы на...
Я учил нижних границ сегодня, и один из студентов спросил о причине названия C . Официальное объяснение состоит в том, что «А» означает «Чередование».AC0AC0AC^0A CAСAC Я смутно помню, как много лет назад мне сказали, что Ник Пиппенгер Стив Кук назвал честь Ника Пиппенджера (класс Ника), а позже Ник...
Укороченная версия. Первоначальное доказательство того, что # 2-SAT является #P -завершенным, фактически показывает, что экземпляры # 2-SAT являются монотонными (без учета отрицаний каких-либо переменных) и двудольными (график, образованный предложениями над Переменный является двудольным графом)...
Мы знаем, что линейные программы (ЛП) могут быть решены точно за полиномиальное время с помощью метода эллипсоидов или метода внутренних точек, таких как алгоритм Кармаркара. Некоторые ЛП с суперполиномиальным (экспоненциальным) числом переменных / ограничений также могут быть решены за...
На большинстве сайтов, которые я посетил, читая эту интересную тему, говорится что-то вроде «единственные степени двух (кроме 2-х самих), которые встречаются в этой последовательности, - это те, которые имеют простой показатель степени» (MathWorld) или «После 2 эта последовательность содержит...
Это продолжение недавнего вопроса, заданного А. Палом: Решение полуопределенных программ за полиномиальное время . Я все еще ломаю голову над фактическим временем выполнения алгоритмов, которые вычисляют решение полуопределенной программы (SDP). Как отметил Робин в своем комментарии к...