LibraryReExportIsNPComplete
From APIDesign
(Difference between revisions)
(New page: Describe the way to convert 3SAT to solution of finding the right configuration from conflicting libraries in a system that can reexport APIs.) |
|||
| Line 1: | Line 1: | ||
| - | + | This page describes a way to convert any [[wikipedia::3SAT]] problem to a solution of finding the right configuration from conflicting libraries in a system that can re-export APIs. Thus proving that the later problem is [[wikipedia::NP-complete]]. | |
| + | |||
| + | == [[wikipedia::3SAT]] == | ||
| + | |||
| + | The problem of satisfying a logic formula remains '''NP'''-complete even if all expressions are written in ''[[wikipedia::conjunctive normal form]]'' with 3 variables per clause (3-CNF), yielding the '''3SAT''' problem. This means the expression has the form: | ||
| + | :(''x''<sub>11</sub> OR ''x''<sub>12</sub> OR ''x''<sub>13</sub>) AND | ||
| + | :(''x''<sub>21</sub> OR ''x''<sub>22</sub> OR ''x''<sub>23</sub>) AND | ||
| + | :(''x''<sub>31</sub> OR ''x''<sub>32</sub> OR ''x''<sub>33</sub>) AND ... | ||
| + | where each ''x'' is a variable or a negation of a variable, and each variable can appear multiple times in the expression. | ||
| + | |||
| + | == Configuration with Re-export == | ||
| + | |||
| + | tbd. | ||
Revision as of 01:01, 15 May 2008
This page describes a way to convert any wikipedia::3SAT problem to a solution of finding the right configuration from conflicting libraries in a system that can re-export APIs. Thus proving that the later problem is wikipedia::NP-complete.
wikipedia::3SAT
The problem of satisfying a logic formula remains NP-complete even if all expressions are written in wikipedia::conjunctive normal form with 3 variables per clause (3-CNF), yielding the 3SAT problem. This means the expression has the form:
- (x11 OR x12 OR x13) AND
- (x21 OR x22 OR x23) AND
- (x31 OR x32 OR x33) AND ...
where each x is a variable or a negation of a variable, and each variable can appear multiple times in the expression.
Configuration with Re-export
tbd.
Follow
