Как сделать запрос из направленного ациклического графа с эксклюзивными подмножествами

Я думаю, что набор вершин, которые вытекают из данного выбора, выглядит сбивающим с толку, потому что на самом деле существует основная проблема оптимизации или удовлетворения: учитывая сборку A, вы можете удовлетворить ее зависимости через B1, B2 или B3, и каждый из этих вариантов тогда имеет его собственные последствия.

Если мы рассматриваем это как проблему логического удовлетворения, то мы могли бы рассмотреть проблему, при которой сборки бывают только двух версий, например A1 или A2. Тогда предложение, такое как (a или b или не c), будет преобразовано в сборку верхнего уровня, которая требует A1 или B1 или C2 - возможно, косвенно через X1, X2 и X3 - и соединение предложений будет преобразовано в верхний верхний сборка уровня, которая требовала всех сборок верхнего уровня. Поэтому я думаю, что если бы вы могли эффективно решить общую проблему, вы могли бы эффективно решить 3-SAT, и тогда P = NP.

Любопытно, что если у вас нет ограничения, что вам разрешена только одна сборка каждого типа (A1, A2 или A3, но более одной за раз), тогда проблема очень легко переводится в предложения Horn (Knuth Vol 4, раздел 7.1. 1 P 57), для которого проблема выполнимости может быть решена эффективно. Для этого вы работаете с инверсией естественных переменных, так что X1 означает, что A1 не включен. Затем, если вы рассматриваете версию предложения Horn как способ ослабить вашу проблему, игнорируя ограничение, согласно которому может поддерживаться не более одной версии каждой сборки, вы получаете механизм, сообщающий вам, что некоторая версия сборки A1 не может быть в решении, потому что X1 = not A1 истинно в основе решения Хорна и, следовательно, истинно в каждом удовлетворительном задании.