Находится проблема разрешения в Полном NP OSGi?

Да.

Подход, взятый в Paper , цитируемые Паскаль, могут быть сделаны для работы с OSGI. Ниже я покажу, как уменьшить какой-либо экземпляр 3-SAT к проблеме разрешения расслоения OSGI. Этот сайт, похоже, не поддерживает математическую обозначение, поэтому я буду использовать такую ​​нотацию, знакомую программистам.

Вот определение проблемы 3 SAT, которую мы пытаемся уменьшить:

Сначала определяют набор атомов пропозициональных атомов и их отрицания A = {A (1), ..., A (k), Na (1), ..., Na (k)}. На более проще языке каждый A (I) является логией, и мы определяем Na (i) =! A (i)

, то 3-синие экземпляры S имеют форму: S = C (1) и ... & C (n )

где C (I) = l (I, 1) | Л (я, 2) | L (i, 3) и каждый l (i, j) представляет собой элемент

, решающий конкретный экземпляр 3-х с SAT включает в себя наличие набора значений, истинного или ложного для каждого A (i) в A, так что S оценивает правду.

Теперь давайте определим пачки, которые мы будем использовать, чтобы построить эквивалентную проблему разрешения. В следующих всех версиях пакета и пакета 0 и импортные версии диапазоны неограниченные, за исключением случаев, когда указано.

• Все выражение S будет представлено Bundle BS
• Каждая пункт C (I) будет представлена ​​расслоением BC (i)
• каждый атом A (j) будет представлен BA (J) ) Версия 1
• Каждый отрицанный атом Na (j) будет представлен Bundle BA (J) версии 2

Теперь для ограничений, начиная с атомов:

BA (J) версии 1
-Экспорт Пакет PA (J) Версия 1
- для каждого пункта C (i), содержащий атом A (j) экспорта PM (I) и добавляю PA (J) в PM (I) использует директиву

BA (J) версии 2
-Экспорт Пакет PA (J) Версия 2
- для каждого пункта C (I), содержащий отрицанный атом Na (j) экспорта PM (I) и добавить PA (J) в PM (I) использует директиву

BC (I)
-Экспорт ПК (I)
-Import PM (I) и добавьте его на использование Директивы ПК (I)
- для каждого атома A (j) в пункте C (I) необязательно импортируют версию PA (j) [1,1] и добавить PA (j) к Директиве использующих PC (I)
-для каждого атома Na (j) в пункте C (i) необязательно импортируют версию PA (j) [2,2] и добавить PA (j) на используемую Директиву экспорта ПК (I)

BS
- Нет экспорта
-для каждого пункта C (I) Импорт ПК (I)
-Для каждого атома A (j) в импорте PA (j) [1,2]

Несколько слов объяснения:

И взаимосвязь между положениями реализуется путем импорта BS от каждого доступа (I) Пакет PC (I), который экспортируется только этим пакетом.

И или отношения работает, потому что BC (I) импортирует пакет PM (I), который экспортируется только связки, представляющими его члены, поэтому, по крайней мере, один из них должен присутствовать, и потому что он необязательно импортирует некоторую версию PA (J) x От каждого пакета, представляющего член, пакет, уникальный для этого расслоения.

Неотношение между Ba (j)Версия 1 и Ba (j) версия 2 применяются , используются ограничения . BS импортирует каждый пакет PA (j) без ограничений версий, поэтому он должен импортировать либо версию PA (j) версии 1 или PA (j) для каждого j. Кроме того, используемые ограничения гарантируют, что любой PA (j), импортированный пункт BC (i), действующим в качестве подразумеваемого ограничения на классное пространство BS, поэтому BS не может быть разрешен, если в его подразумевании появляются оба версии PA (J). ограничения. Поэтому только одна версия BA (j) может быть в решении.

Кстати, есть гораздо простым способом реализации неотношений - просто добавьте Singleton: = True Директива к каждому BA (j). Я не сделал этого таким образом, потому что Директива Singleton редко используется, так что это похоже на обману. Я только упоминаю об этом, потому что на практике нет никаких ОСГИ, которые я не знаю, о необходимости , использует ограничения на основе на основе на основе на основе на основе на основе пакетных ограничений на основе на основе необязательного импорта, поэтому, если вы должны были на самом деле создавать пакеты, используя этот метод, то тестирование их может быть расстраивающим опытом.

Другие замечания:

Уменьшение 3-SAT, которое не использует необязательный импорт, хотя это дольше. Он в основном включает дополнительный слой связки для моделирования дополнительных с использованием версий. Снижение САТ 1-in-3 эквивалентно сокращению до 3-SAT и выглядит проще, хотя я не перешел через него.

Помимо доказательств, которые используют Singleton: = True, все доказательства, которые я знаю о зависимости от транзитивности использующих ограничений. Обратите внимание, что как Singleton: = True, и переходные применения являются несложные ограничения.

Доказательство выше, на самом деле показывает, что проблема разрешения OSGI является NP-полной или хуже. Чтобы продемонстрировать, что нам не хуже, нам нужно показать, что любое решение проблемы может быть проверено в полиноме. Большинство вещей, которые необходимо проверить, являются местными, например Глядя на каждый недооценший импорт и проверка того, что он подключен к совместимому экспорту. Проверка это o (num-local-ограничения). Ограничения на основе Singleton: = True необходимо посмотреть на все синглтонные пучки и убедитесь, что у нее нет одно и то же символическое имя. Количество чеков меньше, чем числовые пучки Num-Bundles. Наиболее сложной частью является проверка того, что используемые ограничения удовлетворены. Для каждого пакета это включает в себя идущий на использование графа, чтобы собрать все ограничения, а затем проверять, что ни один из этих конфликтов с импортом пакета. Любой разумный ходьбовый алгоритм повернулся, когда он столкнулся с проводом или использует отношения, которые он видел раньше, поэтому максимальное количество шагов в прогулке (Num-Wives-In-Framework + NUM-Framework). Максимальная стоимость проверки того, что провод или используемые отношения не ходили ранее, меньше, чем в журнале этого. После того, как были собраны ограниченные пакеты, стоимость проверки согласованности на каждый пакет меньше, чем Num-Imports-In-Bundle NUM-Exports-In-Framework. Все здесь - многочлена или лучше.