минимальные умножения против проблемы покрытия множества

У меня есть множество I = {P1, P2, ..., Pm} и n конечных подмножеств I, обозначаемых через R1,R2,...,Rn следующим образом :

R1 = {P1, P2}

R2 = {P2, P4}

R3 = {P2, P3, P4}

R4 = {P1, P2, P4}

... ..

где Pi обозначает целое число.

Для каждого Ri я хочу вычислить произведение всех его элементов. Моя цель состоит в том, чтобы использовать как можно меньше умножений и делений, разделяя некоторые общие части между Ri (i=1,2,...,n).

Например, если я могу сначала вычислить P2*P4, то этот результат можно использовать для вычисления произведения всех элементов для R3 и R4.

Обратите внимание, что разделение также разрешено. Например, я могу сначала вычислить A=P1*P2*P3*P4, затем использовать A/P1 для вычисления произведения всех элементов для R3 и использовать A/P3 для R4.

Если я хочу использовать минимальные умножения и деления для вычисления всех произведений для каждого подмножества I, будет ли это проблемой покрытия множества? NP-полный? Кстати, не могли бы вы дать формулировку линейной программы Integer, чтобы описать ее так же, как здесь.

Будем признательны за любые предложения!

Редактирование сообщества: Дополнительные допущения:

• деление разрешено, такая же стоимость, как и умножение
• в заданном наборе нет повторяющихся элементов. например R5 = {P1, P1, P1, P2}запрещено