Планар 3SAT является NP-полным. Планарный экземпляр 3SAT - это экземпляр 3SAT, для которого график, построенный с использованием следующих правил, является плоским: добавить вершину для каждого и ¯ х яxixix_ixi¯xi¯\bar{x_i} добавить вершину для каждого предложения CjCjC_j добавить ребро для каждого...
У меня проблема: Покажите, что существует действительное число, для которого не существует ни одной программы, которая работает бесконечно долго и записывает десятичные цифры этого числа. Я полагаю, что это можно решить, сведя его к проблеме остановки, но я понятия не имею, как это сделать. Буду...
Мы знаем , что в N L по Иммерман-Szelepcsenyi теорема теорема и так ы т - с O п п е с т я v я т у есть N L - h a r d, следовательно, s t - n
Такие языки, как являются сокращением много-один. Нетрудно видеть, что имеет полные проблемы. С. Шмитц [1] рассматривает некоторые классы между и . Они представляют полные проблемы для этих классов при специально созданных...
Итак, как известно, проблема решения ILP 0-1 является NP-полной. Показать его в NP легко, а оригинальное сокращение было от SAT; с тех пор было доказано, что многие другие проблемы NP-Complete имеют составы ILP (которые функционируют как сокращение от этих проблем до ILP), потому что ILP очень...
Поскольку целочисленное линейное программирование является NP-полным, существует сокращение Карпа от любой проблемы в NP до него. Я думал, что это подразумевает, что всегда есть формулировка ILP полиномиального размера для любой проблемы в NP. Но я видел статьи по конкретным проблемам NP, где люди...
Проблема 3-Перегородка спрашивает , может ли набор из целых чисел может быть разделена на п наборов из трех чисел таким образом, что каждый набор сумм до некоторого заданного целого числа B . Задача сбалансированного разбиения спрашивает, можно ли разбить 2 n целых чисел на два одинаковых набора...
Определение: уменьшение Карпа Язык является приводимым по Карпу к языку если существует вычислимая функция за полиномиальное время такая, что для каждого , тогда и только тогда , когда .B f : { 0 , 1 } ∗ → { 0 , 1 } ∗ x x ∈ A f ( x ) ∈...
Мне любопытно, есть ли какие-либо полные проблемы в классе сложности Артура-Мерлина. Неизоморфизм графов (GNI) кажется каноническим примером проблемы в AM, но, вероятно, он не полный. Полагаю, мне также интересно, хорошо ли определена «полная» проблема для AM. Так как AM = BP.NP, похоже, что...
Извините, если у этого вопроса есть какой-то тривиальный ответ, который я пропускаю. Всякий раз, когда я изучаю какую-то проблему, которая оказалась неразрешимой, я замечаю, что доказательство основывается на сведении к другой проблеме, которая оказалась неразрешимой. Я понимаю, что это создает...
Я готовлюсь к своему выпускному экзамену по теории вычислений и пытаюсь найти правильный способ ответить на вопрос, верно ли это утверждение для ложного. По определению из можно построить следующее заявление,≤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...
Зоопарк Сложности определяет как класс задач решения, решаемых детерминированной машиной Тьюринга за линейное время.LINLINLIN LIN⊆PLIN⊆PLIN \subseteq P Поскольку HORN-SAT разрешим в (как указано в алгоритмах линейного времени для проверки выполнимости формул рогового высказывания (1984)...
Тестовый раунд Google Hash Code 2015 ( формулировка проблемы ) задал вопрос о следующей проблеме: вход: сетка с несколькими отмеченными квадратами, порог , максимальная площадьT ∈ N A ∈ NMMMT∈ NT∈NT \in \mathbb{N}A ∈ NA∈NA \in \mathbb{N} Выход: наибольшая возможная площадь множества...
У нас было несколько вопросов о связи сокращений Кука и Карпа . Понятно, что сокращения Кука (сокращения Тьюринга за полиномиальное время) не определяют то же понятие NP-полноты, что и сокращения Карпа (сокращения многозначного за полиномиальное время), которые обычно используются. В частности,...
Для рассуждений о таких вещах, как NP-полнота, мы обычно используем многократные сокращения (т.е. сокращения Карпа). Это приводит к таким картинкам: (по стандартным предположениям). Я уверен, что мы все знакомы с такими вещами. Какую картину мы получаем, если работаем с сокращениями Тьюринга (т. Е....
Рассмотрим следующую проблему, входной экземпляр которой представляет собой простой граф и натуральное целое число k .гGGКkk Существует ли множество такое, что G - S двудольный и | S | ≤ к ?S⊆ V( G )S⊆V(G)S \subseteq V(G)G - SG−SG - S| S| ≤k|S|≤k|S| \leq k Я хотел бы показать, что эта проблема...
Является ли машина Тьюринга, которому разрешено чтение и запись символов из бесконечного алфавита, более мощной, чем обычная ТМ (единственное отличие, у машины все еще есть конечное число состояний)? Интуиция говорит мне, что нет, так как вам нужно бесконечное количество состояний, чтобы...
Существует известное и элегантное сокращение от проблемы максимального согласования по двум частям до проблемы максимального потока: мы создаем сеть с исходным узлом , терминальным узлом и одним узлом для каждого сопоставляемого элемента, затем добавляем соответствующие ребра.sssttt Конечно, есть...
Я пытаюсь придумать доказательство для следующего: Для любого языка AAA , существует язык BBB такие , что A≤TBA≤TBA \le_{\mathrm{T}} B , но B ≰TA≰TA\nleq_{\mathrm{T}} A . Я думал о том, чтобы позволить BBB быть ATMATMA_{\mathrm{TM}} , но я понимаю, что не все языки Тьюринга сводимы к...
Допустим, мы знаем, что проблема A сложная, затем мы сводим A к неизвестной проблеме B, чтобы доказать, что B также сложно. В качестве примера: мы знаем, что 3-окраска сложна. Затем мы уменьшаем 3-окраску до 4-окраски. Сочетая один из цветов в 3-х раскрасках, вы получаете 4-х раскраски, поэтому...