Я думаю, что набор вершин, вытекающих из заданного выбора, выглядит сбивающим с толку, потому что на самом деле существует основная проблема оптимизации или удовлетворения: для сборки A вы можете удовлетворить ее зависимости через B1, B2 или B3, и каждый из нихВ этом случае выбор имеет свои собственные последствия.
Если мы рассматриваем это как проблему логического удовлетворения, то мы могли бы рассмотреть проблему, когда сборки бывают только двух версий, например, А1 или А2.Тогда такой пункт, как (a или b или не c), будет преобразован в сборку верхнего уровня, для которой требуется A1 или B1 или C2 - возможно, косвенно через X1, X2 и X3 - и сочетание предложений будет преобразовано в верхний верхнийсборка уровня, для которой требовались все сборки верхнего уровня.Поэтому я думаю, что если бы вы могли эффективно решить общую проблему, вы могли бы эффективно решить 3-SAT, а затем P = NP.
Любопытно, что если у вас нет ограничения, что вам разрешается только одна сборкакаждый тип (А1 или А2 или А3, но более одного за один раз), а затем задача очень легко переводится в предложения Хорна (Кнут, том 4, раздел 7.1.1, стр. 57), для которых проблема выполнимости может быть эффективно решена.Для этого вы работаете с обратными натуральными переменными, так что X1 означает, что A1 не включен.Затем, если вы рассматриваете версию предложения Horn как способ ослабления вашей проблемы, игнорируя ограничение, что может поддерживаться не более одной версии каждой сборки, вы получаете механизм, который сообщает вам, что какая-то версия сборки A1 не может быть в решении, потому что X1 = не А1 верно в ядре решения Хорна и, следовательно, верно в каждом удовлетворительном назначении.