解枚举的延迟、输出与空间

想列出一份很长的结果清单，“明天全部交齐”和“每分钟给下一项”是不同承诺。还有第三个问题：为了连续输出，是否需要先把整份清单存进内存？枚举算法必须分开回答。

结束事件同样重要。已经收到两个答案后，长时间没有第三个，无法判断是全部输出完了还是仍在搜索。空结果时更没有首项可作进度信号，因此定义必须约束确认结束所花的时间。

总量合格，首项仍很慢 ​

输入为一元串 $1^n$，枚举全部 $n$ 位二进制串。算法 A 先空转 $2^n$ 步，然后用二进制计数器依次输出所有 $2^n$ 条记录。总输出长度为 $\mathrm{\Theta }((n+1)2^n)$，总时间为 $O((n+1)2^n)$，因而是输出多项式；但第一条要等 $2^n$ 步，远非输入长度 $n$ 的多项式延迟。

算法 B 不空转，直接从全零开始，每输出一项就递增计数器。每次加一和写一条记录最多用 $O(n+1)$ 位步骤，最后溢出时发结束事件，工作空间也只有 $O(n+1)$。当 $n=0$，答案是唯一一条空串记录，随后结束，而不是零条答案。这个例子同时体现分帧的必要性。

SAT 判定 oracle 支持怎样的流式枚举 ​

对显式声明 $n$ 个变量的 CNF，用 SAT 限制公式理路SAT 的逐变量见证恢复SAT self-reduction · SAT search-to-decision · SAT 自归约只调用返回是或否的SAT判定器，用逐变量限制恢复总赋值，并分开计算查询次数、查询位长、外层成本与无解终止。做深度优先遍历。先询问原式；若否，直接发结束。若是，从空前缀开始，在每个内部节点依次尝试 0、1，把当前公式限制到相应值，只有 oracle 回答可满足才递归进入。到前缀长度 $n$ 时输出该赋值，再返回父节点继续。

每个到达节点都对应一个确有补全的前缀，所以不会在一棵没有答案的子树里继续深搜。叶子显然是满足赋值；每个满足赋值的全部前缀都可补全，算法不会把它剪掉，因而不会漏解。不同叶子对应不同完整比特串，所以无须存储已输出集合也能保证无重复。先 0 后 1 则固定了字典序。

对于

全部输出依次为 010、101。从 010 返回时，前缀 011 不可满足，被剪去；回到根的右支后，100 被剪去、101 被输出，最后前缀 11 被剪去，算法发结束事件。它恢复的是所有赋值，不能用只恢复一份见证的 $n+1$ 总查询界。

延迟证明与空间账本 ​

首个输出前，算法沿至多 $n$ 层向下，每层最多测试两个孩子。相邻两个输出之间，最多回退 $n$ 层并向下 $n$ 层；每个尚未处理的兄弟要么一次询问就被剪掉，要么进入一个已知非空子树，并沿有限深度走向下一份输出。粗略以 $4n+2$ 次 oracle 调用界住每个输出间隔足够；最后一项之后至多回退整条路径并剪去剩余兄弟，收尾也同阶。无解输入只用初次一次询问。

这是相对于 oracle 的多项式延迟，还要加上每次限制和查询写出的多项式成本。若单次实际 SAT 判定时间是 $T(cN)$，间隔上界具有 $\mathrm{poly}(N)+O((n+1)T(cN))$ 的形式；本页没有得到一般 SAT 的普通多项式延迟枚举器。

朴素递归实现每层保留一份大小 $O(N)$ 的限制公式，深度至多 $n$，因此外层工作空间为 $O((n+1)N)$ 位，输出流不回读。一个实现也可通过回滚或重新扫描减少副本，但需要另外证明；不能因深度优先就把存储含糊地记成“常数空间”。如果采用不断加入阻塞子句的方法排除已输出赋值，公式会随输出条数增长，便失去了这里按原输入 $N$ 控制查询大小与空间的账本。

若有一般 SAT 的普通多项式延迟枚举器，且满足本页首项与空集终止界，就可运行到首项或结束来多项式判定 SAT，从而推出 P=NP。这个推论依赖准确的延迟定义；仅知道某个枚举器总会在有限时间给完全部解不够。

“依次枚举再计数”也不会自动产生多项式计数器，因为见证数可能指数多。#P 前缀计数理路计数复杂性类 #PSharp-P · #P可高效验证的见证计数类；由前缀计数构造均匀生成器，并给出近似计数到近均匀采样的完整误差预算。用数量决定均匀采样概率，本页只询问前缀是否非空，输出规则又是字典序；这些接口不能互换。比如在有三个见证的树上，均匀随机选择非空孩子并不一定均匀选择叶子。

共同终点要求复算 010、101 的输出次序，说明首项、下一项、结束三个时刻如何计费，并把暴力 oracle 的内部枚举时间与外层查询次数分开。