Является ли это допустимой задачей математического выражения P или NP?

Прямое сокращение от проблемы с разделами (которая является NP-полной) — при заданном наборе N целые числа S, входными данными для задачи «Действительная математика» будут — элементы S, N-2 оператора «+» и знак «=».

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

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

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

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

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

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

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

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

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

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

ЕСЛИ экземпляр суммы подмножества разрешим, то существует некоторое подмножество целых чисел, которое добавляет к 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 разрешим, ЕСЛИ и ТОЛЬКО ЕСЛИ разрешим соответствующий экземпляр суммы подмножества, поэтому редукция завершена.

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

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

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

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

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