ОК, сначала вы указываете «набор» целых чисел, но набор по определению неупорядочен, так что вы имеете в виду «список» целых чисел.
Кроме того, здесь я сделаю предположение, которое может быть неверным, а именно то, что знак = всегда появляется ровно один раз, между вторым и последним и последним целым числом в вашем списке. Если вы разрешите знак равенства в середине, он станет более сложным.
Вот фактическое доказательство того, что «Действительное математическое выражение» (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 разрешим, ЕСЛИ И ТОЛЬКО ЕСЛИ соответствующий экземпляр суммы поднабора является разрешимым, поэтому сокращение завершено.
РЕДАКТИРОВАТЬ: Сокращение разделов (с комментарием) работает также, и лучше, потому что это позволяет вам ставить знак равенства в любом месте. Ухоженная!