第7回では, の部分集合系 が与えられたときに, が開集合系の定義を満たす( が位相空間になる)かどうかの判定について書きます. 計算量は の要素数を , ワードサイズを として, 時間計算量 , 空間計算量 です. これが多項式時間になるという雰囲気が好きです. あらすじ: を含む最小の位相空間の要素数が であるかを判定すればよい. を含む最小の位相空間と対応する preorder を作り, 縮約し DAG にする. その DAG についてある種の DFS を行い, 開集合の個数を数え上げる. ただし, 個数が を超えたら切り上げる.