Типичные примеры NP-сложных задач (клика, 3-SAT, покрытие вершин и т. Д.) Относятся к тому типу, когда мы не знаем, является ли ответ «да» или «нет» заранее. Предположим, что у нас есть проблема, в которой мы знаем ответ «да», кроме того, мы можем проверить свидетеля за полиномиальное время. Можем...
Относительно потока, Доказывающего, что преобразование из CNF в DNF является NP-Hard (и связанный математический поток ): Как насчет другого направления, от DNF до CNF? Это легко или сложно? На странице 2 этой статьи они, похоже, намекают на то, что оба направления одинаково трудны, когда говорят:...
Я знаю, что проблема количественной булевой формулы для формулы где содержит квантификаторов и только переменные является примером -полной проблемы. Однако мне интересно, существуют ли какие-либо естественные проблемы, известные как -полные, так же, как минимизация контуров является естественной...
Я пытаюсь найти ответы на два вопроса об универсальной машине Тьюринга. Как универсальная машина Тьюринга может моделировать машину Тьюринга, если моделируемая машина имеет большее число состояний? Как универсальная машина Тьюринга может имитировать машину Тьюринга, если на моделируемой машине...
Что означает «в положительной позиции» и «в отрицательной позиции» в контексте теории типов? Единственное, что я понял из поста Боба Харпера на эту тему, это то, что существует связь между полярностью в этом смысле в теории типов и полярностью в логике, но я не знаю, что это за...
Алгоритм Бжозовского можно распространить на автоматы Мура, но его временная сложность в целом экспоненциальна. Есть ли другой алгоритм минимизации автоматов Мура? Какое время работы этих алгоритмов, если таковые...
В синтаксическом анализаторе LR (0) каждое состояние состоит из набора элементов LR (0), которые являются продукцией, аннотированной позицией. В синтаксическом анализаторе LR (1) каждое состояние состоит из набора элементов LR (1), которые являются продукцией, аннотированной позицией и символом...
Есть способ выполнить нечеткий синтаксический анализ (принимает строки даже с опечатками на определенном расстоянии редактирования), с помощью DFA и встроенных автоматов Левенштейна для входного слова. Может ли нечто подобное быть сделано с парсером Earley? Мне трудно понять алгоритм, не говоря уже...
После прочтения достижений Google Deepmind в играх Atari , я пытаюсь понять q-learning и q-network, но я немного запутался. Путаница возникает в концепции дисконтного фактора. Краткое резюме того, что я понимаю. Глубокая сверточная нейронная сеть используется для оценки значения оптимального...
Я читаю «Душу новой машины» Трейси Киддер, где команда Data General разрабатывает новую машину (под кодовым названием «Eagle», позже названную MV / 8000). Это 32-битное расширение предыдущей архитектуры (16-битное Eclipse). Кажется, одной из вращающихся тем является то, что они не хотят создавать...
Я читал «Операционные системы» Гальвина и натолкнулся на следующую строчку: Однако не все небезопасные государства находятся в тупике. Небезопасное состояние может привести к тупику Может кто-нибудь объяснить, пожалуйста, как тупик! = Небезопасное состояние? Я также поймал ту же самую линию здесь...
Я пытаюсь понять, как работает Slab Allocation и почему он отличается или лучше, чем обычный пейджинг. Я нашел эту диаграмму, которая, на мой взгляд, была бы полезна, если бы она имела больше объяснений Некоторые вопросы: Что представляют собой элементы размером 3 КБ и 7 КБ? Должны ли они быть...
Этот вопрос является чем-то вроде обратного к предыдущему вопросу о множествах, сформированных из операций над множествами на NP-полных наборах: Если множество , являющееся результатом объединения, пересечения или декартового произведения двух разрешимых множеств и является NP-полным, является ли...
Это, вероятно , глупая мысль, но предположим , что у нас есть компьютер , который запрограммирован для выполнения бесконечную последовательность расчетов и предположим , что расчет занимает 1 / 2 я секунд. Тогда этот компьютер может выполнять бесконечное количество вычислений за конечное...
Я попытался выполнить следующее упражнение, но застрял, пытаясь найти все критические пары . У меня есть следующие вопросы: Как мне узнать, какая критическая пара произвела новое правило? Как я узнал, что нашел все критические пары? Пусть где бинарный, унарный, а константа....
Недавно я прочитал действительно интересную запись в блоге Google Research Blog, рассказывающую о нейронной сети. В основном они используют эту нейронную сеть для решения различных задач, таких как распознавание изображений. Они используют генетические алгоритмы, чтобы «развить» веса аксонов. В...
Если P=NPP=NP\mathbf{P} = \mathbf{NP} , то есть L=NLL=NL\mathbf{L} = \mathbf{NL} ? Я задаю этот вопрос, потому что для других недетерминированных классов кажется, что P=NPP=NP\mathbf{P} = \mathbf{NP} всегда устанавливает, что они равны своим детерминированным...
Я знаю, что языки, которые можно определить с помощью регулярных выражений, и языки, распознаваемые DFA / NFA (конечными автоматами), эквивалентны. Также не существует DFA для языка . Но все это можно записать с помощью регулярных выражений (в этом отношении любого нерегулярный язык может быть) ,...
Для заданного набора точек и радиуса . Что представляет собой сложность поиска точки с большим числом точек на расстоянии, меньшем, чем . Например, тот, который максимизирует ?x1,…,xn∈R2x1,…,xn∈R2x_1, \ldots, x_n \in \mathbb{R}^2rrrrrr∑ni=11∥x−xi∥≤r∑i=1n1‖x−xi‖≤r\sum_{i=1}^n \mathbb{1}_{\|x - x_i\|...
Википедия говорит, что объединение по рангу без сжатия пути дает сложную временную сложность O(logn)O(logn)O(\log n) , и что объединение по рангу и сжатию пути дает сложную временную сложность (где - обратная величина функции Аккермана). Однако в нем не упоминается время сжатия пути без ранга...