Алгоритм машины Тьюринга за полиномиальное время считается эффективным, если его время выполнения, в худшем случае, ограничено полиномиальной функцией входного размера. Мне известен сильный тезис Черча-Тьюринга: Любая разумная модель вычислений может быть эффективно смоделирована на машинах...
У меня есть домашнее задание, от которого я некоторое время ломал голову, и я буду благодарен за любые подсказки. Речь идет о выборе известной проблемы, NP-полнота которой доказана, и построении перехода от этой проблемы к следующей проблеме, которую я назову DGD (диагностика направленного графа)....
Предположим, мне дан конечный набор точек на плоскости, и меня просят нарисовать дважды дифференцируемую кривую через , чтобы ее периметр был как можно меньше. Предполагая, что и , я могу формализовать эту проблему следующим образом: С ( Р ) р я р я = ( х я , у я ) х I < х я +...
Тестовый раунд Google Hash Code 2015 ( формулировка проблемы ) задал вопрос о следующей проблеме: вход: сетка с несколькими отмеченными квадратами, порог , максимальная площадьT ∈ N A ∈ NMMMT∈ NT∈NT \in \mathbb{N}A ∈ NA∈NA \in \mathbb{N} Выход: наибольшая возможная площадь множества...
Я готовлюсь к своему выпускному экзамену по теории вычислений и пытаюсь найти правильный способ ответить на вопрос, верно ли это утверждение для ложного. По определению из можно построить следующее заявление,≤m≤m\leq_m w∈A⟺f(w)∈B→w∉A⟺f(w)∉Bw∈A⟺f(w)∈B→w∉A⟺f(w)∉Bw \in A \iff f(w) \in B \rightarrow w...
Я дал множество , целое число , и неотрицательные целые числа . Моя проблема состоит в нахождении непересекающиеся подмножества из такие , что:A≜{1,…,k}A≜{1,…,k}A\triangleq\{1,\ldots,k\}s⩽ks⩽ks\leqslant kaijaija_{ij}sssSjSjS_j{1,…,k}{1,…,k}\{1,\ldots,k\} ⋃sj=1Sj=A⋃j=1sSj=A\bigcup_{j=1}^s S_j=A ; и...
Из Википедии : Тип вычислительной проблемы: Наиболее часто используемые проблемы - это проблемы с решением . Однако классы сложности могут быть определены на основе функциональных проблем, проблем с подсчетом, оптимизационных задач, проблем с обещаниями и т. Д. Я также видел, что определения...
Можно понять ваш вопрос двумя способами, согласно определению «дополнение КЛЛ». Случай A: Дополнение к CFL - это класс всех языков, которых нет в CFL. Формально, В этом случае намного больше, чем , у него даже есть языки, которых нет в и т. Д. Но, возможно, это не то, что вы имели в...
Зоопарк Сложности определяет как класс задач решения, решаемых детерминированной машиной Тьюринга за линейное время.LINLINLIN LIN⊆PLIN⊆PLIN \subseteq P Поскольку HORN-SAT разрешим в (как указано в алгоритмах линейного времени для проверки выполнимости формул рогового высказывания (1984)...
Есть ли алгоритм для решения следующей задачи: При заданной машине Тьюринга которая определяет язык L , существует ли машина Тьюринга M 2, решающая L так , что t 2 ( n ) = o ( t 1 ( n ) ) ?M1M1M_1LLLM2M2M_2LLLt2(n)=o(t1(n))t2(n)=o(t1(n))t_2(n) = o(t_1(n)) Функции и t 2 являются наихудшим временем...
Я знаю, что максимальное независимое множество на кубических графах без треугольников является NP-полным. Является ли он еще NP-полным, если нам требуется, чтобы независимый набор имел размер точно ?|V|/2|V|/2|V|/2 В основном, ДА экземпляр задачи о независимом множестве в задаче о кубах без...
Например, я знаю, что нерегулярный язык находится в A C 0 . Я хотел бы знать больше примеров, как
Учитывая заданий , для выполнения каждого задания требуется раз.J 1 , J 2 , . , , , J п Г я > 0 , Т я ∈ NnnnJ1,J2,...,JnJ1,J2,...,JnJ_1,J_2,...,J_nTi>0,Ti∈NTi>0,Ti∈NT_i > 0, T_i \in N Каждое задание должно быть предварительно обработано и постобработано одной машиной M, которая может...
Учитывая тот факт , что - путь перечисления является # Р-полной задачи, может ли быть эффективные методы , которые вычисляют (или , по меньшей мере , приблизительно) средняя длина - пути без перечисления их? Что если пути разрешены для пересмотра вершин?т с тsssTTtsssTTt Соответствующие результаты...
Как я понимаю, задача присваивания находится в P, поскольку венгерский алгоритм может решить ее за полиномиальное время - O (n 3 ). Я также понимаю, что задача присваивания - это целочисленная задача линейного программирования , но на странице Википедии говорится, что это NP-Hard. Для меня это...
Я прочитал несколько раз, что невозможно эффективно перевернуть ответ NDTM. Однако я не понимаю, почему. Например, учитывая NDTM который выполняется в , этот текст (раздел 3.3) утверждает, что неясно, как другой NDTM может определить за время, как перевернуть...
Мне интересно, есть ли какие-нибудь -hard проблемы, которые являются «полиномиальными» в среднем случае. Я думаю, что есть два способа интерпретировать это?NпNпNP Если , может ли быть алгоритм, решающий задачу N P -hard, с амортизированным (в среднем случае) временем работы O ( n k ) для константы...
Пусть будет некоторой проблемой подсчета, которая известна как # P -Complete .ΠΠ\PiPPP Означает ли это , что является P X -Жесткий (т.е. не PTAS для проблема существует , если P = N P...
Является ли проблема определения того, является ли данное булево выражение выполнимым в вычислительном отношении отличным от фактического нахождения решения выражения? Другими словами, есть ли другой способ найти, что данное выражение выполнимо без явного определения «правильных настроек» для...
Существуют ли какие-либо известные алгоритмы, которые корректно выводят «да» для NP-полной задачи без неявной генерации сертификата? Я понимаю, что легко превратить оракула выполнимости в искатель удовлетворяющих назначений: просто итерируйте по переменным, каждый раз запрашивая оракула...