SATの解空間連結性判定問題 (CONN-SAT) とは, 論理式の充足解集合により誘導されるハミングキューブの部分グラフが, 連結かどうかを判定する問題である. 充足可能性問題 (SAT) が論理式の種類 (Horn SAT, XOR SAT, 2SAT, 3SAT等) によって計算複雑性が変わるのと同様, CONN-SATの計算複雑性も論理式の種類によって分類できる. 本講演ではCONN-SATの計算複雑性の分類に関する研究を概説する. また, 論理式がk-CNF (CONN-SATがPSPACE完全) の場合に対する指数時間アルゴリズムを紹介する. 本講演は, 牧野和久 氏, 山本真基 氏との共同研究に基づく.