Вопросы с тегом «decision-problem»

Вопрос в какой-то формальной системе с ответом "да" или "нет".

64
Законодательство NP-полное?

Я хотел бы знать, была ли какая-либо работа, связывающая правовой кодекс со сложностью. В частности, предположим, что у нас есть проблема решения «Учитывая этот закон и этот конкретный набор обстоятельств, виновен ли ответчик?» К какому классу сложности он относится? Есть результаты, которые...

28
Генерация комбинаций из набора пар без повторения элементов

У меня есть набор пар. Каждая пара имеет форму (x, y), так что x, y принадлежат целым числам из диапазона [0,n). Итак, если n равно 4, то у меня есть следующие пары: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) У меня уже есть пары. Теперь я должен построить комбинацию, используя n/2пары, чтобы ни одно из...

28
Почему пустой тип C не аналогичен пустому / нижнему типу?

Википедия, а также другие источники, которые я обнаружил в списке voidтипа C как тип единицы, а не пустой тип. Мне кажется, что это сбивает с толку, так как мне кажется, что оно voidлучше подходит под определение пустого / нижнего типа voidНасколько я могу судить, ценности не обитают . Функция с...

26
Оптимизация версии решения проблемы

Этот вопрос был перенесен из теоретического обмена стеков информатики, потому что на него можно ответить в обмене стеков информатики. Мигрировал 7 лет назад . Известно, что каждая проблема оптимизации / поиска имеет эквивалентную проблему решения. Например, проблема кратчайшего пути версия для...

25
Почему эта неразрешимая проблема в NP?

Очевидно, что в NP нет неразрешимых проблем. Однако, согласно Википедии : NP - это совокупность всех задач решения, для которых в случаях, когда ответ «да», есть [... доказательства, которые] проверяются за полиномиальное время с помощью детерминированной машины Тьюринга. [...] Говорят, что...

24
Различают процедуру принятия решения против решателя SMT и средства доказательства теорем против решателя ограничений

Эти термины смущают меня. Насколько я понимаю SAT решатель: решить выполнимость логики высказываний (используя DPLL или локальный поиск). Процедура принятия решения - это процедура определения выполнимости некоторой разрешимой теории первого порядка. SMT-решатель - это SAT-решатель + процедура...

21
Как можно проверить задачу коммивояжера за полиномиальное время?

Так что я понимаю идею, что решение проблемы определяется как Есть ли путь P такой, что стоимость ниже, чем C? и вы можете легко проверить это, проверив полученный вами путь. Однако что, если нет пути, который соответствует этим критериям? Как бы вы проверили ответ «нет», не решив проблему TSP с...

18
Почему нет алгоритмов аппроксимации для SAT и других задач решения?

У меня NP-полное решение проблемы. Учитывая пример проблемы, я хотел бы разработать алгоритм, который выводит ДА, если проблема выполнима, и НЕТ, в противном случае. (Конечно, если алгоритм не является оптимальным, он будет делать ошибки.) Я не могу найти никаких приближенных алгоритмов для таких...

18
Алгоритм проверки, является ли язык контекстно-свободным

Существует ли алгоритм / систематическая процедура для проверки того, является ли язык свободным от контекста? Другими словами, учитывая язык, указанный в алгебраической форме (подумайте о чем-то вроде ), проверьте, является ли язык контекстно-свободным или нет , Представьте, что мы пишем...

16
В чем разница между «Решением» и «Проверкой» в теории сложности?

В « Теории вычислений Майкла Сипсера» на странице 270 он пишет: P = класс языков, для которых членство может быть решено быстро. NP = класс языков, для которых членство может быть проверено быстро. В чем разница между «решено» и...

14
Существует ли эффективный алгоритм эквивалентности выражений?

например, ?xy+x+y=x+y(x+1)xy+x+y=x+y(x+1)xy+x+y=x+y(x+1) Выражения взяты из обычной школьной алгебры, но ограничены арифметическим сложением и умножением (например, ), без инверсий, вычитания или деления. Буквы являются переменными.2+2=4;2.3=62+2=4;2.3=62+2=4; 2.3=6 Если это поможет, мы можем...

12
Существует ли эффективный тест для принятия NFA подмножества другого NFA?

Итак, я знаю, что проверка того, является ли обычный язык рRR подмножеством обычного языка SSS , разрешима, поскольку мы можем преобразовать их оба в DFA, вычислить R ∩ S¯R∩S¯R \cap \bar{S} , а затем проверить, является ли этот язык пустым. Однако, поскольку это требует преобразования в DFA,...

12
Проблема почтовой корреспонденции в NP?

Я только что прочитал несколько страниц в книге Сипсера «Введение в теорию вычислений о проблеме почтовой корреспонденции» и думаю, что PCP на самом деле находится в NP. Сертификатор составляет: для конфигурации входного ворса конкатенации т 1 , т 2 , . , , , t n как строка t и конкатенация b 1 ,...

11
Является ли равенство двух DFA решаемой проблемой?

Итак, учитывая два DFA, является ли проблема обнаружения, если они генерируют один и тот же язык, разрешимой проблемой? Я уже знаю, что равенство двух КЛЛ не является разрешимым а как насчет равенства двух ДФА? учитывая, что большинство проблем с DFAs разрешимы, это тоже...

11
Алгоритм проверки правильности языка

Существует ли алгоритм / систематическая процедура для проверки правильности языка? Другими словами, учитывая язык , заданный в алгебраической форме (думаю , что - то вроде ), проверить , является ли регулярным или не язык. Представьте, что мы пишем веб-сервис, чтобы помочь студентам со всеми...

11
Самый длинный цикл состоит из двух циклов

Является ли следующая задача NP-полной? (Я предполагаю, что да). Входные данные: - неориентированный граф, в котором множество ребер можно разложить на два простых цикла, не пересекающих ребра (они не являются частью входных данных).k∈N,G=(V,E)k∈N,G=(V,E)k \in \mathbb{N},G=(V,E) Вопрос: существует...

11
Можно ли решить, является ли данный алгоритм асимптотически оптимальным?

Есть ли алгоритм для решения следующей задачи: При заданной машине Тьюринга которая определяет язык 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 являются наихудшим временем...

11
-алгебра в качестве входных данных для алгоритма

Я хочу уточнить, что значит дать алгебру в качестве входных данных для алгоритма, и я не нашел много литературы по этому поводу. Итак, сначала я хочу спросить, можете ли вы порекомендовать книгу или статью, которая посвящена теме анализа сложности алгебр над полями и четко определяет решение...

10
присвоение номера

Для заданных чисел таких что , существует ли присвоение чисел который является перестановкой такой, чтоA 1 ≤ A 2 ≤ . , , ≤ к к Σ я = 1 А я = K ( 2 K + 1 ) я 1 , я 2 , . , , , Я 2 к 1 , 2 , . , , , 2 кkkkA1≤A2≤...≤AkA1≤A2≤...≤AkA_1 \leq A_2 \leq ... \leq...