Это задание является последующим вопросом к предыдущему посту Робина Котари о результатах определения полиномиального времени . В частности, я заинтересован в том, чтобы увидеть некоторые доказательства твердости для задач, которые, как считается, имеют примерно нижних границ, и я говорю грубо,...
Название говорит само за себя. Вот Акинатор и 20Q . Принцип этих игр состоит в том, чтобы задавать пользователю ряд вопросов, касающихся некоторой сущности, выбранной пользователем. А потом выясните, что это за сущность. Суть алгоритма состоит в том, чтобы находить «самый полезный вопрос» в каждом...
Есть 4 различных ограничения, которые мы можем иметь при определении Random K-SAT. 1) Общее количество литералов в заданных предложениях в точности равно K или AT большинству K 2) Данный литерал может использоваться с заменой или без замены в одном и том же предложении (A или A или A) 3) Данная...
Я переместил этот вопрос из stackoverflow, где id не получил ответов. У нас был похожий вопрос , является ли JSON регулярным : JSON и XML часто называют языками без контекста - они оба определяются в основном формальной грамматикой в EBNF. Однако это верно только для JSON, как определено в RFC...
Широко известно, что формулы CNF можно условно разделить на 2 широких класса: случайный и структурированный. Структурированные формулы CNF, в отличие от случайных формул CNF, демонстрируют некоторый порядок, демонстрируя паттерны, которые вряд ли могут произойти случайно. Тем не менее, можно найти...
Этот вопрос похож на NP-сложные задачи на деревьях : Существует большое количество NP-полных задач, которые можно отследить на рефератах . Есть ли какие-либо известные проблемы, которые остаются NP-полными, если они ограничены Cographs? Чтобы быть более точным, меня интересуют примеры, в которых...
Допустим, мы обнаруживаем инопланетные цивилизации, которые могут отправлять и получать сообщения, используя межзвездный цифровой канал связи. (Скажем, с помощью модулированных радиоволн, лазерных импульсов, изменения положения звезд на различных орбитах.) Предположим, мы решили установить с ними...
Что известно о следующей проблеме? Для набора функций : f : { 0 , 1 } n → { 0 , 1 } найдите наибольшую подгруппу S ⊆ C с учетом ограничения VC-Dimension ( S ) ≤ k для некоторого целого числа k .СCCе: { 0 , 1 }N→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\}S⊆ CS⊆CS \subseteq C( S) ≤...
Я хотел бы написать математические доказательства, используя некоторый помощник по доказательствам. Все будет написано с использованием логики первого порядка (с равенством) и естественного вывода. Фон - теория множеств (ZF). Например, как я мог написать следующее доказательство? Аксиома: ∀ х ∀ у(...
Я ищу хороший справочник для кратчайших путей узкого места. В частности, учитывая вершины s и t в неориентированном графе с весом ребер, вы хотите кратчайший путь от s до t, где длина пути - это максимальное ребро на этом пути. Это можно решить за время O (n + m), найдя средний вес ребра и...
Пусть x1,…,xnx1,…,xnx_1, \ldots, x_n - точки на плоскости R2R2\mathbb{R}^2 . Рассмотрим полный граф с точками в виде вершин и весами ребер . Вы всегда можете найти вес, который составляет не менее \ 2 2 от общего веса? Если нет, то какая константа должна заменить \ frac 2 3 ?2∥xi−xj∥2‖xi−xj‖2\|x_i...
Рассмотрим следующую проблему: Учитывая набор из положительных чисел { a 1 , … , a n }, в которых k ≥ 3 является константой, мы хотим разбить набор на m подмножеств размера k так, чтобы произведение суммы каждого подмножества максимальноn=kmn=kmn = k m{a1,…,an}{a1,…,an}\{ a_1, \dots, a_n \}k≥3k≥3k...
Есть ли обзор (из бумаги, главы книги, учебника, ссылок, ...) семантики различных функций языка программирования? Первоначально я был поражен возможностями D здесь http://www.digitalmars.com/d/2.0/comparison.html Я хотел бы посмотреть, что я мог бы получить отсюда, хотя я задал похожий вопрос по...
Есть несколько конкурирующих понятий "разреженного графа". Например, встраиваемый в поверхность граф можно считать разреженным. Или график с ограниченной плотностью ребер. Или график с высоким обхватом. График с большим расширением. Граф с ограниченной шириной дерева. (Даже в подполе случайных...
В алгоритме Tiny Encryption : Различные кратные магической константы используются для предотвращения простых атак, основанных на симметрии раундов. Магическая постоянная, 2654435769 или 9E3779B9 16 , выбрана равной 232/ ϕ232/ϕ2^{32}/ \phi , где ϕ - золотое сечение. Какими свойствами обладает 232/...
Я уже читал примеры формул в CTL, но не в LTL и наоборот, но у меня возникают проблемы с умственным пониманием формул LTL, и на самом деле в чем
Я ищу модальные логики, которые аксиоматизируются конечным набором аксиом глубины модальной вложенности, и чья проблема выполнимости / выводимости вряд ли будет в PSPACE. Без ограничения глубины модального вложения это не проблема, см., Например, PDL. Но, по-видимому, при доказательстве, например,...
Мы можем думать о колмогоровской сложности строки xxx как о длине самой короткой программы PPP и вводим , что . Обычно эти программы взяты из некоторого полного набора Тьюринга (например, может быть описанием машины Тьюринга, или это может быть программа на LISP или C). Даже когда мы смотрим на...
Учитывая последовательность из чисел, можно ли ее отсортировать с помощью O ( n ln n ) сравнений и O ( n ) перестановок / ходов? Любой указатель на публикации по этому вопросу или контраргументы, показывающие нижнюю границу Ω ( n ln n ) , поможет.nnnO(nlnn)O(nlnn)O(n \ln...
Если представляет собой график с максимальной степенью 3 и является минор H , то G является топологическим минор H .граммGGЧАСHHграммGGЧАСHH Википедия цитирует этот результат из «Теории графов» Дистеля. В последней версии книги он указан как Опора 1.7.4. В книге нет доказательств или цитирования....