Immerman-Szelepcsényi Theorem: For any function $S(n)\geq \log n$,

$\textnormal{NSPACE}(S(n))=\textnormal{co-NSPACE}(S(n))$

$\textnormal{CSL}=\textnormal{NSPACE}(n)$

$\forall L\in\textnormal{NSPACE}(S(n)),\bar{L}\in\textnormal{NSPACE}(S(n))$

$\forall x\in L,\not\exists \textnormal{a path from }C_{start} \textnormal{ to }C_{accept}$

$(s,t)$-UNCONN 问题：给定一个图$G$ 和其中两个结点$s,t$，如果存在一条 path 从$s\rightarrow t$，则输出 NO。否则输出 YES。

（其实上述误区就在于，“怎么把一个 NTM 的 accept 和 reject 交换”。它无法在很低的时间复杂度内完成（$NP=?coNP$ 未知）（因为需要知道所有 branch reject 才能 accept），但可以在很低的空间复杂度内完成$NSPACE=coNSPACE$ 也就是这个定理证明的。）

$R(s,t,l)=\begin{cases} 1 & \textnormal{there exists a path from s to t, and its length}\leq l\\ 0 & \textnormal{otherwise} \end{cases}$

1. 非确定性地创建$2^{|V|-1}$ 个 branches，每个 branches 猜测了一个 bit mask（譬如$m=101011$）表示了对于每个$u\in V-\{t\}$$s\rightarrow u$ 是否存在一条长度$\leq l$ 的 path。$m(u)=1$ 表示猜测有，反之则没有。

2. 对于每一个 branch，以及 bit mask 中为 1（$m(u)=1$）的那些点$u\in V-\{t\}$，我们用$(s,t)$-CONN 的图灵机去判定$s\rightarrow u$ 是否存在一条长度$\leq l$ 的边。

更具体地，这一步可以直接运行$(s,t)$-CONN 的 NTM，如果该 NTM accept 则状态转移进入第 3 步；如果该 NTM 有任意分支 reject，则全局也 reject，说明这个 branch 的 bit mask 猜错了。

3. 能进入这一步，说明每个$m(u)=1$ 的点$u$ 都猜正确的了。但是对于$m(u)=0$ 的那些点，我们并没有办法得知，是否真的不存在$s\rightarrow u$ 的长度$\leq l$ 的边，因为不存在是困难的。

我们存下来$\textnormal{count}^*=$ bit mask 中$1$ 的个数。

1. 现在假设我们知道了一个数 "$count=s$$\leq l$ 步能到达的点的数量 "。（具体计算方法会在后面讨论）

（注意，$count$$count^*$ 差异就在于，$count^*$ 是去除了$t$ 后、在当前分支猜测情况下算出来的，不一定是对的，但一定小于等于正确的值，而且一定有一个分支等于正确的值。）

然后我们讨论：

• $count^*=count$，则 accept 并输出 0。此时$count^*$ 是正确的值，而且$V$$V-\{t\}$ 中，$s$$\leq l$ 步能到达的点的数量是一样的，故输出 0。

• $count^*< count-1$，则直接 reject。说明我们 bit mask 猜错太多了。因为正确的$count^*$ 最少为$count-1$

• $count^*=count-1$，此时需要分类讨论：

• $s\rightarrow t$ 真的存在一条长$\leq l$ 的 path，则说明$count^*$ 猜测正确，则需要输出 1。
• $s\rightarrow t$ 真的不存在一条长$\leq l$ 的 path，则说明$count^*$ 猜测错误，存在一个点$u$$s\rightarrow u$ 有一条长$\leq l$ 的 path，但我们把他猜成了$m(u)=0$

为了判别以上两种情况，我们直接运行判定$(s,t)$-CONN 的 NTM，去判定是否存在$s\rightarrow t$ 有一条长度$\leq l$ 的 path。若该 NTM accept，则直接输出 1。若该 NTM 任意分支 reject，则全局 reject 这个分支。说明$count^*$ 猜错了，我们期待猜对了的那个分支去输出结果。
{"ft_lang_label":"__label__zh","ft_lang_prob":0.9951647,"math_prob":0.9999504,"size":2527,"snap":"2023-40-2023-50","text_gpt3_token_len":1910,"char_repetition_ratio":0.10305192,"word_repetition_ratio":0.0,"special_character_ratio":0.22754253,"punctuation_ratio":0.015306123,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999696,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-09-23T21:43:57Z\",\"WARC-Record-ID\":\"<urn:uuid:d22a7b07-7181-439e-b702-f19da8239b7a>\",\"Content-Length\":\"114082\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:90654bff-726e-456b-86c1-e69931362e0f>\",\"WARC-Concurrent-To\":\"<urn:uuid:2947ec2f-90a3-449a-9422-3130f5896c94>\",\"WARC-IP-Address\":\"185.199.109.153\",\"WARC-Target-URI\":\"https://www.subonan.com/2023/05/02/Immerman-Szelepcsenyi-Theorem/\",\"WARC-Payload-Digest\":\"sha1:2SLA3FC3PGJEGBWUS6TKPB2CGRE3U6FR\",\"WARC-Block-Digest\":\"sha1:3S2AFEUYBJZCZVNTJLOR3DN56HZVLPTE\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-40/CC-MAIN-2023-40_segments_1695233506528.3_warc_CC-MAIN-20230923194908-20230923224908-00401.warc.gz\"}"}