这个问题是NP完全的，因此不知道是否存在多项式时间解。（在实践中可能很容易的标准附加条件等都适用。）一种可能的减少来自 3SAT。
假设我们有一个 3SAT 实例，例如 (a ∨ b ∨ c) ∧ (¬a ∨ ¬b ∨ ¬c)。我将展示如何使用“小工具”来构建您的问题的实例。在开始之前，将 3SAT 问题改写为 (a1 ∨ b1 ∨ c1) ∧ (¬a2 ∨ ¬b2 ∨ ¬c2) 以及 a1 = a2, b1 = b2, and c1 = c2; 即，使变量的每次出现都是唯一的，但随后添加相同变量的不同出现必须相等的条件。
首先，我们确保您必须选择第一行中的数字 0，以便我们以后可以将其用作您必须避免的“哨兵”。
0 0 0
现在，我们构建一个执行 a1 = a2 规则的小工具：（_这里的下划线是每次使用这个小工具时的一个新的唯一编号）
0 _ 0
a1 0 ¬a1
a2 0 ¬a2
由于第一行，您必须避免使用 0。这意味着您要么选择路径“a1, a2”，要么选择路径“¬a1, ¬a2”；前者对应于（有点令人困惑）将 a 设置为 false，而后者对应于将 a 设置为 true。这是因为我们的子句小工具真的很简单，因为我们只是简单地写下子句，例如（_这里每次都是一个新变量）：
0 _ 0
a1 b1 b2
或者
0 _ 0
¬a1 ¬b1 ¬b2
最后，由于您只使用了 a1 和 ¬a1 等中的一个，我们让您拿走您没有使用的那些：
0 _ 0
a1 ¬a1 0
现在，这并不完全奏效，因为 a1 和 ¬a1 中的一个可能已在变量选择小工具中使用，而另一个可能已在子句中使用。@i因此，我们为您可以使用的每个子句包含一个新变量，而不是其中一个变量。所以如果变量 a1 出现在第 1 条中，我们有
0 _ 0
a1 ¬a1 @1
这是原始 3SAT 子句翻译的完整输出（突出显示对应于将 a 和 b 设置为 true、c 为 false 并从第一个子句中选择 a 的路径），左侧是数字，右侧是光泽。小工具被重新排序（第一个子句小工具，然后是每个变量，相等小工具，然后是未使用的小工具），但这并不重要，因为它们无论如何都是独立的。
0 0 < 0 . . < .
0 8 < 0 . _ < .
2 < 4 6 a1 < b1 c1
0 16 < 0 . _ .
11 13 15 < -a2 -b2 -c2<
0 17 < 0 . _ < .
2 0 3 < a1 . -a1<
10 0 11 < a2 . -a2<
0 18 < 0 . _ < .
2 3 1 < a1 -a1 @1 <
0 19 < 0 . _ .
10 < 11 9 a2 < -a2 @2
0 20 < 0 . _ < .
4 0 5 < b1 . -b1<
12 0 13 < b2 . -b2<
0 21 < 0 . _ < .
4 < 5 1 b1 < -b1 @1
0 22 < 0 . _ < .
12 < 13 9 b2 < -b2 @2
0 23 < 0 . _ < .
6 < 0 7 c1 < . -c1
14 < 0 15 c2 < . -c2
0 24 < 0 . _ < .
6 7 < 1 c1 -c1< @1
0 25 < 0 . _ < .
14 15 9 < c2 -c2 @2 <
（如果您希望整个事情是方形的，只需在每行的末尾添加一堆零。）很有趣的是，无论您如何解决这个问题，从本质上讲，您都在解决 3SAT 问题。
在我的帖子末尾是一个仓促编写的 Perl 程序，它从表单的输入中生成您的一个问题
a b c
-a -b -c
问题的结果实例中的变量数为11C + V + 1。给程序-r开关以产生光泽而不是数字。
# Set useful output defaults
$, = "\t"; $\ = "\n";
# Process readability option and force sentinel
my $r = "0";
if( $ARGV[0] =~ /-r/ ) { shift; $r = "."; }
print $r, $r, $r;
# Clause gadgets
my( %v, %c, $m, $c );
$m = 1;
while( <> ) {
my( @v, @m );
$c = $m++;
chomp; @v = split;
for my $v ( @v ) {
push @{$v{strip($v)}}, -1; # hack, argh!
push @m, ($r ? $v.@{$v{strip($v)}} : $m + neg($v));
$c{($r ? (strip($v).@{$v{strip($v)}}) : $m)} = $c;
$v{strip($v)}->[-1] = ($r ? (strip($v).@{$v{strip($v)}}) : $m);
$m += 2 unless $r;
}
print $r, newv(), $r;
print @m;
}
# Variable gadget
for my $v ( sort keys %v ) {
# Force equal
print $r, newv(), $r;
for my $n ( @{$v{$v}} ) {
print $n, $r, ($r ? "-".$n : $n+1);
}
# Unused
for my $n ( @{$v{$v}} ) {
print $r, newv(), $r;
print $n, ($r ? "-".$n : $n+1), ($r ? "\@".$c{$n} : $c{$n});
}
}
# Strip leading -
sub strip {
my( $v ) = @_;
return substr $v, neg($v);
}
# Is this variable negative?
sub neg {
my( $v ) = @_;
return "-" eq substr( $v, 0, 1 );
}
# New, unused variable
sub newv {
return "_" if $r;
return $m++;
}