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

Question

Допустим, у нас есть проблема с суммой подмножества со списком { $ x_1, x_2, x_3, ... x_n $ } и вес $ w $ , с некоторыми из $ x_i <0 $ .Есть ли известный способ в многочленом времени, чтобы преобразовать эту проблему в эквивалентную проблему, но со всеми $ X_I \ GEQ 0 $ ?И если там нет, возможно ли там такой алгоритм?

Answer 1

Оба варианта являются NP-Complete, поэтому такое уменьшение обязательно существует: определениеNP-полнота гарантирует это.

Если вы хотите явное восстановление, вы можете уменьшить один на другой (уменьшить до 3SAT, используя теорему Кука, затем уменьшить 3SAT к другому, используя свою NP-полноту).В результате сокращение будет уродливым, хотя, поэтому я подозреваю, что это не может быть то, что вы ищете.

Если вы хотите простое и естественное сокращение, я не уверен, как добиться этого.