>102
>私は、これは距離が0または1であるとは限らないため決定問題と言えず、NP完全と言えないということと解釈していたが、
>例えば2進数で距離を表して距離の10桁目は0であるか?
>見たいな事をyes/noで答えること繰り返す事で比較できるような決定問題と見なせるようにも思えました。

1行目が正解。
詳しくないので細かいことは言えないが、繰り返しの話は探索版から決定版への自己帰着の話に近いと思う。