Приведенный список из n положительных целых чисел (n четный), разделите список на два подвычислителя таким образом, чтобы разность между суммами целых чисел в двух подсписках была минимизирована. Будет ли это проблемой NP-полной или NP-трудной проблемой?NP-полный или NP-жесткий?
TL; DR - это жесткий диск.
это оптимизационная версия проблемы с разделом. проблема раздела решает, если данный список положительных целых чисел можно разделить на 2 подмножества, так что суммы подмножеств равны. версия оптимизации запрашивает минимальную разницу (как вы просили).
проблема раздела np-complete, но оптимизация является np hard.
вы можете прочитать больше об этих проблемах в вики: https://en.wikipedia.org/wiki/Partition_problem