Проблема удовлетворенности является, конечно, фундаментальной проблемой в теоретической CS. Я играл с одной версией проблемы с бесконечным количеством переменных. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Базовая настройка. Пусть непустое и, возможно, бесконечное множество...
Недавний подход к созданию децентрализованной онлайн-валюты под названием биткойн вызвал некоторый интерес. Цель состоит в том, чтобы иметь возможность переводить валюту без центрального органа и без двойных расходов или подделок. Их подход заключается в том, чтобы все узлы в сети пытались...
Квантовые вычисления - это активная область исследований, целью которой является использование квантовой физики (например, квантовой запутанности) для повышения эффективности компьютеров (не изменяет тезис Черча-Тьюринга ). Каковы наиболее значимые эксперименты, которые были проведены для...
Предположим, вам дан связный простой неориентированный граф H. Проблема H-свободного среза определяется следующим образом: Для простого неориентированного графа G существует ли разрез (разбиение вершин на два непустых множества L, R) такой, что графы, индуцированные множествами разрезов (L и R), не...
Сетевой коммутатор (название придумано) выполнен с тремя типами узлов: один начальный узел один конечный узел один или несколько узлов коммутатора Узел коммутатора имеет 3 выхода: влево, вверх, вправо; имеет два состояния L и R и целевое состояние TL или TR . Каждый переключатель может быть пройден...
На большинстве сайтов, которые я посетил, читая эту интересную тему, говорится что-то вроде «единственные степени двух (кроме 2-х самих), которые встречаются в этой последовательности, - это те, которые имеют простой показатель степени» (MathWorld) или «После 2 эта последовательность содержит...
Каковы наиболее известные методы циклической свертки длины над небольшим полем, т.е. когда | F | « П ? Меня особенно интересуют поля постоянного размера или даже . Общие утверждения и ссылки об асимптотической эффективности высоко ценятся.nnn|F|≪n|F|≪n|\mathbb{F}| \ll nF=F2F=F2\mathbb{F} =...
Читая статью об использовании алгебраических методов для обнаружения некоторых индуцированных подграфов, кажется, что реберный идеал является важным инструментом, соединяющим коммутативную алгебру и теорию графов. Поскольку я не знаком с вычислениями алгебраических объектов, есть ли хорошие ссылки...
Насколько я понимаю, все известные детерминированные сводные правила для симплексных алгоритмов имеют конкретные входные данные, для которых алгоритму требуется экспоненциальное время (или, по крайней мере, не полиномиальное), чтобы найти оптимальный. Давайте назовем эти случаи «патологическими»,...
Я пытаюсь выяснить, есть ли какие-либо общие результаты или примеры, касающиеся NP-полноты проблемы поиска второго решения NP-полной задачи. Точнее, меня интересуют любые проблемы следующего вида: Учитывая решение для экземпляра NP-полной задачи, есть ли решение для ?SSSяяIS'≠ SS'≠SS' \neq SяяI...
Я новичок в теории языков программирования и ищу хороший ресурс по формальной семантике языков программирования. Специально ищет структурную операционную семантику. Я получил несколько рекомендаций книги. Но я ищу ресурс на более начальном уровне. Особенно приветствуются учебники, веб-сайт и...
Контекст: отношения между логикой и автоматами Теорема Бучи гласит, что монадическая логика второго порядка над строками (MSO) охватывает класс регулярных языков. Фактически доказательство показывает, что экзистенциальный MSO ( или EMSO ) над строками достаточен для захвата обычных языков. Это...
Поскольку термин перегружен, сначала дается краткое определение. Poset - это множество наделенное частичным порядком ≤ . Для двух элементов a , b ∈ X , мы можем определить x ∨ y (join) как их наименьшую верхнюю границу в X и аналогично определить x ∧ y (meet) (join) как наибольшую нижнюю...
Что если что-либо известно о параметризованной сложности вычисления числа пересечений графа (наименьшее число кликов, необходимых для охвата всех его ребер)? Давно известно, что он является NP-полным, и это, очевидно, FPT, потому что у него есть ядро: если вы можете покрыть граф кликами, то...
Я читал о классах графов , для которых Изоморфизм графов ( ) находится в P . Одним из таких случаев являются графы ограниченной валентности (максимально над степенью каждой вершины), как описано здесь . Но я нашел это слишком абстрактным. Я был бы благодарен, если бы кто-нибудь мог предложить мне...
Известен ли следующий класс графов в литературе? Класс графов параметризуется натуральными числами и и содержит каждый граф такой, что для каждой вершины подграф индуцируется на всех вершинах на расстоянии не более от в имеет длину не более .dddTTtG = ( V, E)граммзнак равно(В,Е)G=(V,E)v ∈ Vv∈Вv\in...
Известно, что минимальный размер цепей, функцию четности, в точности равен . Нижняя оценка доказательства основана на методе исключения ворот.U2U2U_23 ( n - 1 )3(N-1)3(n-1) Недавно я заметил, что метод исключения затвора хорошо работает и для недетерминированных цепей, и мы можем доказать нижнюю...
Хорошо известно, что если вы бросите n шаров в n корзин, то в самой загруженной корзине, скорее всего, будет шариков. В общем, можно спросить о шарах в корзинах. В статье из RANDOM 1998, опубликованной Раабом и Стегером, это подробно рассматривается, показывая, что с ростом вероятность того, что...
Я учил нижних границ сегодня, и один из студентов спросил о причине названия C . Официальное объяснение состоит в том, что «А» означает «Чередование».AC0AC0AC^0A CAСAC Я смутно помню, как много лет назад мне сказали, что Ник Пиппенгер Стив Кук назвал честь Ника Пиппенджера (класс Ника), а позже Ник...
Мне сказали, что есть несколько хороших алгоритмов полиномиального времени для аппроксимации числа простых путей в ориентированном графе от заданной начальной вершины до заданной конечной вершины t . Кто-нибудь знает хорошую ссылку на эту тему?sssTTt Справочная информация: подсчет точного числа...