この問題はNP完全であるため、多項式時間の解があるかどうかはわかりません。（実際に簡単である可能性があるなどの標準的な条件がすべて適用されます。）1つの可能な削減は3SATからです。
（a∨b∨c）∧（¬a∨¬b∨¬c）のような3SATインスタンスがあるとします。「ガジェット」を使用して問題のインスタンスを作成する方法を示します。始める前に、3SAT問題を（a1∨b1∨c1）∧（¬a2∨¬b2∨¬c2）とa1 = a2、b1 = b2、および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などのいずれか1つしか使用していないため、使用していないものを自由に使用できます。
0 _ 0
a1 ¬a1 0
a1と¬a1の一方が変数選択ガジェットで使用され、もう一方が句で使用された可能性があるため、これは完全には機能しません。@iそのため、変数の1つではなく、各句に新しい変数を含めることができます。したがって、変数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問題を解決していることを確認するのは楽しいことです。
私の投稿の最後に、フォームの入力から問題の1つを生成する急いで書かれた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++;
}