首页 文章

OSGi NP-Complete中的分辨率问题是什么？

提问于
浏览 次
25

解决问题的方法在OSGi R4 core specification的模块化章节中有所描述 . 这是一个约束满足问题，当然也是一个有效解决的挑战性问题，即不是蛮力 . 主要的复杂因素是使用约束，它具有非局部效应，并且可以自由地删除可选导入以获得成功的解决方案 .

NP-Completeness在StackOverflow上处理elsewhere .

关于这个问题的答案已经有很多猜测，所以请避免猜测 . 好的答案将包括一个证明，或者，如果没有这个，那就是一个引人注目的非正式论

这个问题的答案对于构建OSGi解析器的项目很有 Value ，包括Eclipse Equinox和Apache Felix开源项目，以及更广泛的OSGi社区 .

osgi

3 回答

  • 26

    是 .

    所引用的edos paper Pascal采用的方法可以与OSGi一起使用 . 下面我将展示如何将任何3-SAT实例减少为OSGi包解析问题 . 这个网站似乎不支持数学符号，所以我将使用程序员熟悉的那种符号 .

    以下是我们试图减少的3-SAT问题的定义：

    首先将A定义为一组命题原子及其否定A = {a（1），...，a（k），na（1），...，na（k）} . 在更简单的语言中，每个a（i）是一个布尔值，我们定义na（i）=！a（i）

    然后3-SAT实例S具有以下形式：S = C（1）＆...＆C（n）

    其中C（i）= L（i，1）| L（i，2）| L（i，3）和每个L（i，j）是A的成员

    求解特定的3-SAT实例涉及为A中的每个a（i）找到一组值，真或假，使得S求值为真 .

    现在让我们定义我们将用于构造等效分辨率问题的包 . 在以下所有包和包中，版本均为0，导入版本范围不受限制，除非指定 .

    • 整个表达式S将由Bundle BS表示

    • 每个条款C（i）将由一个包BC（i）表示

    • 每个原子a（j）将由束BA（j）版本1表示

    • 每个否定原子na（j）将由BA（j）版本2表示

    现在为了约束，从原子开始：

    BA（j）第1版
    -export包PA（j）版本1

    • 每个条款C（i）包含原子a（j）导出PM（i）并将PA（j）添加到PM（i）的使用指令

    BA（j）第2版
    -export包PA（j）版本2

    • 对于每个条款C（i）包含否定原子na（j）导出PM（i）并将PA（j）添加到PM（i）的使用指令

    BC（ⅰ）

    • 出口PC（i）
      -import PM（i）并将其添加到PC（i）的使用指令
    • 对于C（i）中的每个原子a（j），可选择导入PA（j）版本[1,1]并将PA（j）添加到PC（i）导出的uses指令中
    • 对于C（i）中的每个原子na（j），可选择导入PA（j）版本[2,2]并将PA（j）添加到PC（i）导出的uses指令中

    BS

    • 没有出口
    • 对于每个条款C（i）进口PC（i）
    • 对于A中的每个原子a（j）进口PA（j）[1,2]

    几句解释：

    子句之间的AND关系是通过从每个BC（i）导入仅由该捆绑包导出的包PC（i）来实现的 .

    OR关系有效，因为BC（i）导入的包PM（i）仅由代表其成员的包导出，因此它们中至少有一个必须存在，并且因为它可以选择从每个包中导入一些PA（j）版本x表示成员的捆绑包，该捆绑包唯一的包 .

    BA（j）版本1和BA（j）版本2之间的NOT关系由使用约束强制执行 . BS导入每个包PA（j）而没有版本约束，因此它必须为每个j导入PA（j）版本1或PA（j）版本2 . 此外，使用约束确保子句束BC（i）导入的任何PA（j）充当BS的类空间的隐含约束，因此如果PA（j）的两个版本出现在其隐含中，则无法解析BS . 限制 . 因此，解决方案中只能有一个版本的BA（j） .

    顺便提一下，有一种更简单的方法来实现NOT关系 - 只需将singleton：= true指令添加到每个BA（j） . 我没有这样做，因为很少使用单例指令，所以这似乎是作弊 . 我只是提到它，因为在实践中，没有OSGi框架我知道实现在可选导入时正确使用基于包的约束，所以如果你实际使用这种方法创建包，那么测试它们可能是令人沮丧的经历 .

    其他评论：

    减少不使用可选输入的3-SAT也是可能的，尽管这会更长 . 它基本上涉及一个额外的bundle层来模拟使用版本的可选性 . 减少1-in-3 SAT相当于减少到3-SAT并且看起来更简单，尽管我还没有逐步完成它 .

    除了使用singleton：= true的证明之外，我所知道的所有证据都取决于使用约束的传递性 . 请注意，singleton：= true和transitive使用都是非本地约束 .

    该上面的证据实际上表明OSGi解决问题是NP完全或更糟 . 为了证明它不会更糟，我们需要证明可以在多项式时间内验证问题的任何解决方案 . 大多数需要检查的事情都是本地的，例如：查看每个非可选导入并检查它是否连接到兼容的导出 . 验证这些是O（num-local-constraints） . 基于singleton的约束：= true需要查看所有单例包并检查没有两个具有相同的包符号名称 . 检查次数少于num-bundlesnum-bundles . 最复杂的部分是检查是否满足使用约束 . 对于每个捆绑包，这涉及遍历使用图以收集所有约束，然后检查这些约束是否与捆绑包的导入冲突 . 任何合理的步行算法都会在遇到之前遇到的线路或使用关系时返回，因此步行中的最大步数是（框架中的num-wires-in-framework num-uses-in） . 检查电线或使用关系之前没有走过的最大成本小于此日志 . 一旦收集了受约束的包，每个包的一致性检查的成本就低于num-imports-in-bundlenum-exports-in-framework . 这里的一切都是多项式或更好的 .

    回复于
  • 2
    回复于
  • 0

    从记忆中我认为这篇论文包含了演示，对不起之前没有检查过 . 这是我打算复制的其他链接，我确信会在第48页提供演示：http://www.edos-project.org/bin/download/Main/Deliverables/edos%2Dwp2d1.pdf

    回复于

相关问题