Является это “Допустимое математическое выражение” проблемой P или NP?

Есть два свойства, которые должны быть выполнены, чтобы быть NP Complete.

Проблема решения C является NP-полной, если:

1. C находится в NP, и
2. ] Каждая задача из NP сводится к C за полиномиальное время.

Мы установили 1. 2 вытекает из того факта, что каждая задача из NP сводится к 3SAT, а 3SAT сводится к текущей проблеме.

Следовательно, это NP-complete.

(править) Ответ на комментарий ниже:

Я докажу, что SAT сводится к текущей проблеме, а поскольку 3SAT сводится к SAT, результат следует.

Входная формула - это сочетание следующих выражений:

(x ₁ V x ₂ V x ₃ V ... x _n V y ₁ )

(x ₁ V x ₂ V x ₃ V ...x _n V y ₂ )

(x ₁ V x ₂ V x ₃ V. .. x _n V y ₃ )

.

.

.

(x ₁ V x ₂ V x ₃ V ... x _n V y ₆₄ )

где каждый y _i является логическим на основе того, какой порядок операторов применяется между всеми x _i .x _n V y ₆₄ )

где каждый y _i является логическим значением в зависимости от того, какой порядок операторов применяется между всеми x _я есть.x _n V y ₆₄ )

где каждый y _i является логическим значением в зависимости от того, какой порядок операторов применяется между всеми x _я есть. т.е. y _i может принимать в общей сложности 4x4x4x4x1 значений (при условии, что только +, -, x, / являются операторами, а = всегда является последним оператором; это можно изменить, если набор операторов изменен на включить другие операторы)

Если ни одно из выражений не является истинным, тогда полное выражение будет оцениваться как ЛОЖЬ, и нет возможности проверить, если мы не заменим все возможные значения, то есть от x ₁ до x _n как числа n и y ₁ через y ₆₄ как различные способы применения операторов (это обеспечивает порядок)

Это преобразование выполняется в POLY-времени, и данная логическая формула является выполнимой, если и только если математическое выражение является допустимым и т. Д.

Кто-нибудь заметил недостаток?

Сейчас нет времени на полный ответ, но вы можете описать сокращение этой проблемы до Задачи о рюкзаке .

Используя динамическое программирование, вы может достичь временного решения псевдополиномиального . Обратите внимание, что это не противоречит тому факту, что проблема действительно NP Complete.

На самом деле это не ответ на ваш сложный вопрос, но ваша проблема немного похожа на проблема Обратный отсчет . Быстрый поиск нашел эту бумагу: http://www.cs.nott.ac.uk/~gmh/countdown.pdf

На данный момент у меня нет времени на разработку доказательства, но догадка подсказывает мне, что его может не быть в P. Вы можете определить грамматику для арифметики, а затем это Вопрос сводится к поиску правильного дерева синтаксического анализа, которое использует все эти терминалы. я полагаю , что эта проблема находится в NP, но не в P.

Хорошо, сначала вы указываете "набор" целых чисел, но набор по определению неупорядочен, поэтому вы имеете в виду "список" целых чисел.

Кроме того, я собираюсь составить предположение, которое может быть неверным, а именно, что знак = всегда появляется ровно один раз, между предпоследним и последним целым числом в вашем списке. Если вы разрешите знак равенства посередине, это станет более сложным.

Вот фактическое доказательство того, что «Действительное математическое выражение» (VME) является NP-полным. Мы можем сделать сокращение из Сумма подмножества . ОБРАТИТЕ ВНИМАНИЕ, что определение суммы подмножества в Википедии требует, чтобы подмножество было непустым. Фактически, это правда, что более общая проблема суммы подмножества, допускающей пустые подмножества, является NP полной, если желаемая сумма также является частью ввода. Я не предоставлю это доказательство, если его не попросят. Учитывая экземпляр суммы подмножества {i_1, i_2, ..., i_n} вместе с желаемой суммой s , создайте следующий экземпляр VME:

{0, i_1, 0, i_2, 0, ..., i_n, s}, {+, *}, {=}

ЕСЛИ экземпляр подмножества sum разрешима, то есть некоторое подмножество целых чисел, которое складывается в 0. Если целое число i1 является частью суммы, добавьте его с соответствующим ему нулем (сразу слева) и если i1 не является частью суммы, умножьте ее. Между каждым нулем и членом справа вставьте знак сложения.

Взяв пример из Википедии

{−7, −3, −2, 5, 8}

, где {−3, −2, 5} суммируется до 0, мы бы закодировали его как

{0, -7, 0, -3, 0, -2, 0, 5, 0, 8, 0}

и результирующее выражение будет

{0*7 + 0 + -3 + 0 + -2 + 0 + 5 + 0*8 = 0}

Теперь нам также нужно показать, что любое решение этого экземпляра VME приводит к решению экземпляра суммы подмножества. Это проще, чем вы думаете. Когда мы смотрим на полученное выражение, мы можем сгруппировать числа на те, которые умножаются на 0 (в том числе как часть умножения по цепочке), и те, которые не умножаются. Любое число, умноженное на ноль, не включается в окончательную сумму. Любое число, которое не умножается на ноль, должно быть добавлено в окончательную сумму.

Итак, мы показали, что этот экземпляр VME разрешим, ЕСЛИ и ТОЛЬКО ЕСЛИ соответствующий экземпляр подмножества sum разрешим, так что сокращение завершено.

РЕДАКТИРОВАТЬ: Сокращение раздела (с комментарием) также работает, и лучше, потому что оно позволяет вам ставить знак равенства где угодно. Отлично!

Любое число, умноженное на ноль, не включается в окончательную сумму. Любое число, которое не умножается на ноль, должно быть добавлено в окончательную сумму.

Итак, мы показали, что этот экземпляр VME разрешим, ЕСЛИ и ТОЛЬКО ЕСЛИ соответствующий экземпляр подмножества sum разрешим, так что редукция завершена.

РЕДАКТИРОВАТЬ: Сокращение раздела (с комментарием) также работает, и лучше, потому что оно позволяет вам ставить знак равенства где угодно. Отлично!

Любое число, умноженное на ноль, не включается в окончательную сумму. Любое число, которое не умножается на ноль, должно быть добавлено в окончательную сумму.

Итак, мы показали, что этот экземпляр VME разрешим, ЕСЛИ и ТОЛЬКО ЕСЛИ соответствующий экземпляр подмножества sum разрешим, так что редукция завершена.

РЕДАКТИРОВАТЬ: Сокращение раздела (с комментарием) также работает, и лучше, потому что оно позволяет вам ставить знак равенства где угодно. Отлично!

и лучше, потому что позволяет ставить знак равенства где угодно. Отлично!

и лучше, потому что позволяет ставить знак равенства где угодно. Отлично!

Кажется, что-то вроде путаницы насчет того, как проверить NP-полноту. NP-полная задача в определенном смысле не менее сложна, чем любая другая проблема в NP. Предположим, мы сравнивали с 3SAT, как это пытаются сделать некоторые плакаты.

Итак, сокращение данной проблемы до 3SAT ничего не доказывает. Тогда верно, что если 3SAT можно решить эффективно (что означает P = NP), данная проблема может быть решена эффективно. Однако, если данная проблема может быть решена эффективно, то, возможно, она соответствует только легким частным случаям 3SAT.

Нам пришлось бы свести 3SAT к данной задаче. Это означает, что нам нужно будет составить правило для преобразования произвольных задач 3SAT в примеры данной проблемы, таким образом, чтобы решение данной проблемы указывало нам, как решить проблему 3SAT. Значит, 3SAT не может быть сложнее данной задачи. Поскольку 3SAT является наиболее сложным из возможных, данная проблема также должна быть наиболее сложной из возможных.

Уменьшение из проблемы разделения работает. Эта проблема работает следующим образом: для данного мультимножества S целых чисел, можем ли мы разделить его на два непересекающихся подмножества, которые включают в себя каждый член S, так что суммы непересекающихся подмножеств равны?

Для этого мы построим последовательность, начинающаяся с 0, содержащая каждый элемент S, а затем 0. Мы используем {+, -} в качестве набора операций. Это означает, что каждый элемент S будет либо добавлен, либо вычтен до итога до 0, что означает, что сумма добавленных элементов такая же, как сумма вычтенных элементов.

Следовательно,