NL・P・NP問題における決定問題の入力同士の関係がどのように計算複雑性に関係してくるかを，決定問題における部分入力の互換性の構造を解析することにより明らかにする．NL・P・NP問題は入力の部分入力を異なる部分入力に置き換えても出力が変化しない場合があるという対称性を持つ．この対称性の構造は，問題全体で汎用的なものか／特定の入力のみの局所的なものか，対称性自体に互換性のある並列的なものか／順序により非互換となる包含的なものか，という特徴で分類することができる．
本稿では計算モデルとして否定標準回路を用いてこれらの部分入力の対称構造の解析を行った．