重置字(或同步字)概念最早可追溯到20世纪60年代，它相当于重启命令．当不知道设备的当前状况而须要恢复对其控制时，就可考虑使用重置字．比如，在基于模型的反应式系统测试中，须要使用大量测试用例来测试系统行为与设计模型是否一致，每当运行下一个测试用例前都须重启设备，于是可以执行重置字以完成任务[1]．在生物信息计算领域[2]和抗错哈夫曼编码[3]都引入了重置字的思想．文献[4]指出，从可重置自动机的应用角度出发，算法和复杂性问题至关重要．实际应用中总希望得到最短重置字，然而求解最短重置字却是DP-完全的[5]．文献[6-7]结合多核CPU和GPU并行化现有启发式算法，提高了算法性能．这些优化主要借助硬件的进步，而非理论上的改进．求解重置字先要判定给定的自动机是否可重置，目前最快的判定算法是O(n2)[8]，其中n为自动机状态数，是否存在更快的算法尚不清楚，但大多数文献认为二次算法是理论上最好的．于是对于能否找出比O(n2)更快的算法，或能否提供理论上的证据说明当前算法就是最快的值得研究．自动机重置判定问题的对偶是道路着色问题．对于道路着色问题，文献[9]将算法由O(n3)改进到O(n2)，迄今尚未发现更快的算法．在复杂性下界领域，有研究在指数时间猜想[10](exponential time hypothesis，ETH)和强指数时间猜想[11](strong ETH，SETH)下证明了复杂性类P中许多问题的条件下界，比如，用于相似性度量的编辑距离(edit distance，ED)和最长公共子序列(longest common subsequence，LCS)问题，这两个问题目前已有的算法复杂度与已证明的条件下界一致[12-13]．若条件下界优于现有算法复杂度，则说明算法还有改进余地，否则算法很大可能不可改进．正如文献[14]提及的，具有O(nt)时间算法的子集求和(Subset Sum)问题，直到算法的时间复杂度改进至O(tpoly(logt))才与理论上已证明的条件下界符合．Subset Sum问题是指，给定含n个正整数的集合X和目标值t，是否存在X的子集使得其元素之和正好等于t．同样地，须考虑有限自动机重置判定问题和道路着色问题的下界是否与现有算法的复杂度符合．本研究主要结论是有限自动机重置判定问题不存在亚二次多项式算法，否则ETH不成立．1.1　符号说明对于集合X，用|X|表示集合的基数．对于字母表Σ，用Σ*表示由字母表中字母构成的所有有限字(序列)的集合，包含空字ε．有关复杂度度量标记，一般用f(⋅)和g(⋅)表示函数，log(⋅)底数缺省时取2，poly(⋅)表示多项式函数，称O(na-η)是关于n的亚α次多项式复杂度，其中η0为实数．相比O记号，O*记号忽略了关于n的多项式因子poly(n)．1.2　有限自动机及其重置问题定义1 有限自动机．一般将有限自动机A定义为五元组(Q,Σ,δ,qinit,F)，其中：Q为有限状态集；Σ为有限字母表；δ:Q×Σ→Q为变迁函数；qinit为初始状态；F为终止状态集．记L(A)为有限自动机A接受的语言．自动机的底层图指删除自动机变迁上的标记所得的有向图．如果δ为完全函数，即∀q∈Q,∀a∈Σ，δ(q,a)均有定义，也就是|δ(q,a)|0，那么称自动机是完全自动机．如果∀q∈Q,∀a∈Σ，有|δ(q,a)|≤1，那么称自动机是确定自动机．完全确定有限自动机是|δ(q,a)|=1的情况．记δ(S,a):=∪q∈Sδ(q,a)，其中S⊆Q，a∈Σ．可将变迁函数扩展为δ:Q×Σ*→Q，具体定义如下，δ(q,w):=q    (w=ε);δ(δ(q,a),w')    (w=aw'),式中：q∈Q；a∈Σ；w,w'∈Σ*．相应地，δ(S,w):=∪q∈Sδ(q,w)．定义2 重置字．对于完全确定有限自动机A，如果存在字w∈Σ*使得∀q,q'∈Q，有δ(q,w)=δ(q',w)，那么称w是自动机A的重置字(或同步字)，称自动机A是可重置的(或可同步的)．当讨论重置问题时，习惯上不考虑qinit和F，常将自动机记为三元组A=(Q,Σ,δ)．若无特殊说明，以下有限自动机指完全确定有限自动机．对自动机定义见文献[15]．问题1 有限自动机重置判定问题．对于有限自动机A=(Q,Σ,δ)，将判定自动机A是否可重置的问题定义为有限自动机重置判定问题．1.3　道路着色问题问题2 道路着色问题．对于有向强连通图G=(V,E)，其中V为顶点集，E为边集，能否找到一种边的着色(或标记)方案，将图G转化成可重置的有限自动机A．此时图G对应自动机A的底层图．该问题定义为道路着色问题．图1给出了出度为2的有向图着色方案，由此可得到一个可重置的有限自动机，其中：红色对应弧a；蓝色对应弧b．不难看出序列aaa是一个重置字．图2则给出了该自动机所对应的对自动机，其任意状态执行序列aaa后均可到达{q3}．10.13245/j.hust.240205.F001图1有限自动机重置判定问题和道路着色问题示例10.13245/j.hust.240205.F002图2图1自动机所对应的对自动机1.4　细粒度复杂性理论细粒度复杂性理论[14]关注问题的精确运行时间界限．对于所有实数η20，如果问题B2不能在O(t(|x|β-η2)时间内求解，那么复杂性类P内问题B1不能在O(|x|α-η1)时间内求解，其中x为问题B1的输入，α和β为常数，t(∙)一般为多项式或指数函数，称O(t(|x|β)为问题B2的条件下界．定义3 细粒度归约[14]．对于判定问题B1和B2及对应的时间下界tB1和tB2，从(B1,tB1)到(B2,tB2)的细粒度归约是满足以下条件的算法，给定B1的实例IB1计算B2的实例IB2使得：a．IB1是对B1回答为是的实例，当且仅当IB2是对B2的回答为是的实例；b．对于任意实数η20，存在实数η1使得(tB2(|IB2|))1-η2=O((tB1(|IB1|))1-η1)；c．对于某个实数γ0，归约的运行时间是O(tB1((|IB1|))1-γ)．此外，细粒度归约具有传递性．ETH和SETH与可满足性(satisfiability，SAT)问题有关，二者定义见文献[10-11]．2 二次多项式下界及其证明本节若无特殊说明，n表示自动机状态数或有向图顶点数．特别地，在多个自动机语境下，n表示自动机的状态数上界．引理1 不存在实数0η1使得k个有限自动机的交(非空)问题有O(nk-η)时间算法，其中k≥2，除非ETH不成立[16-17]．引理2 道路着色问题有O(n2)时间算法[9]．2.1　重置判定问题下界及其证明定理1 有限自动机重置判定问题有O(|Σ|n2)时间算法，而且是NL-完全的，其中Σ为字母表(当|Σ|取常数时，算法为O(n2)时间)．证明思路．由于自动机A是可重置的，当且仅当∀p,q∈Q存在融合字v∈Σ*使得δ(p,v)=δ(q,v)[8]，于是可通过搜索每对状态的融合字来求解，如果有状态对无法融合，那么自动机不可重置．算法首先构造A的对自动机A2，其大小为O(n2)，构造可在O(|Σ|n2)时间完成；然后在A2上检查每个状态{p,q}是否有到达某个状态q0的路径，实现可采用逆邻接表存储，以含有n个状态q0的队列为搜索起点集合，搜索是否能够达到剩余(n2-n)/2个状态{p,q}，直到覆盖所有变迁或耗尽队列中所有起点．由于A2含变迁数为|Σ|(n2+n)/2，这一步可在O(|Σ|n2)时间完成．如图1和2的例子，图2右侧6个{p,q}类型的状态，均可通过序列a，aa或aaa到达q3．对于NL-难的证明，可从图的可达性问题出发构造归约加以证明．证明 O(|Σ|n2)时间算法不再证明，具体见文献[8]．对于复杂性结论，首先证明NL-难．归约的起点是对自动机A2=(Q',Σ,δ')对应底层图上的可达性问题，即状态{p,q}到状态q0之间是否存在可达路径，其中q0,{p,q}∈Q'．已知：可达性问题是NL-完全的．而有限自动机重置判定问题相当于至多询问poly(N)次状态{p,q}到状态q0之间是否存在可达路径，其中N=(n2+n)/2是对自动机A2的状态数．多次询问不会额外增加存储开销，因此归约还是对数空间归约．于是，有限自动机重置判定问题是NL-难的．接着证明该问题属于NL，只须给出一个非确定的消耗对数空间存储的算法．由于文献[8]给出的时间复杂度为O(|Σ|n2)的广度优先搜索算法实际上相当于上述多次询问可达性问题，而可达性问题是NL-完全的，是有非确定性对数空间算法的，因此有限自动机重置判定问题也存在非确定性对数空间算法．于是，有限自动机重置判定问题属于NL．定理1的NL-难结论可理解为较粗的复杂性下界．后文定理3中的O(n2)下界是更精确的运行时间下界．定理2 存在由两个自动机的交问题到有限自动机重置判定问题的细粒度归约．证明思路．通过构造细粒度归约来证明．证明 设Ai=(Qi,{0,1},δi,qi0,Fi)为完全确定有限自动机，其中i=1,2，不妨设A1的状态数最多，含有n个状态(为方便证明，考虑大小为2的字母表)．从A1和A2出发构造完全确定自动机B=(QB,ΣB,δB)，使得语言L(A1⋂A2)≠∅当且仅当B可重置．自动机B的构造过程如下：QB:=Q1⋃Q2∪{t}；ΣB:=Σ⋃{2}={0,1,2}．接着给出变迁函数δB的构造规则．对于自动机A1和A2，删除所有的从终止状态q∈Fi出发的变迁，保留从其他状态出发的变迁．增加如下变迁：(1) ∀q∈∪i=1,2Fi，δB(q,0)=t，δB(q,1)=t；(2) ∀q∈∪i=1,2Qi，δB(q,2)=qi0；(3) ∀a∈ΣB，δB(t,a)=t．图3给出了两个自动机交问题归约到有限自动机重置判定问题的示意图，其中：红色圆圈表示自动机A1和A2的终止状态，q10和q20分别为A1和A2的初始状态；黑色细线表示的变迁是构造中新增的变迁，标记为字母表{0，1，2}中的字母，新增状态t．10.13245/j.hust.240205.F003图3两个自动机交问题归约到有限自动机重置判定问题首先，证明如果语言L(A1⋂A2)≠∅，那么自动机B是可重置的．设存在字w∈Σ*使得w∈L(A1⋂A2)，那么∀q∈QB，δ(q,2⋅w⋅0)=t和δ(q,2⋅w⋅1)=t．以δ(q,2⋅w⋅0)为例，这是由于      δ(q,2⋅w⋅0)=δ(δ(q,2),w⋅0)=δ((qi0,w),0)=δ(q',0)=t,其中q'∈Fi．显然2⋅w⋅0或2⋅w⋅1是B的一个重置字，于是自动机B是可重置的．然后，证明如果自动机B是可重置的，那么语言L(A1⋂A2)≠∅．如果B是可重置的，那么存在字重置字w∈ΣB*．由于从状态t出发无法到达其他状态，因此可以断定B不论处于哪个状态，执行w后到达的状态一定是t．故状态t是自动机B得到重置后的状态．而除t之外的其他状态要达到t，只能先经过自动机A1或A2的终止状态，然后再执行符号0或1才行．由于不存在从自动机A1中的状态到A2中的状态的变迁，反之也不存在从自动机A2中的状态到A1中的状态的变迁，即两个自动机A1和A2中的状态相互不可达．对于自动机B上的任意状态q，都能通过执行某个字w到达t，一定执行了形式上如2⋅w'⋅0或2⋅w'⋅1这样的字，明显w'既被自动机A1接受，也被自动机A2接受．所以存在w'∈Σ*是L(A1⋂A2)中的字，那么L(A1⋂A2)≠∅．最后，指出归约满足定义3．条件a已通过证明语言L(A1⋂A2)≠∅当且仅当B可重置得到．由于|QB|=|Q1|+|Q2|+1=O(n)，|ΣB|=|Σ|+1=3，|δB|=O(|δ1|)=O(|ΣB|n)，前面假设A1的状态数大于等于A2的，因此自动机B的大小与A1的大小呈线性关系，这意味着归约的构造可在关于A1大小的线性时间内完成．于是，存在某个实数η0使得上述归约的运行时间O(n)=O((n2)1-η)，由于两个自动机交问题存在O(n2)的算法．条件c满足．两个自动机的交问题存在O(n2)的算法，同时自动机重置判定问题也存在O(n2)的算法．对于任何实数η20，显然存在对应的η10使得O(((2n)2)1-η2)=O((n2)1-η1)，因此条件b满足．定理3 不存在实数0η21使得有限自动机重置判定问题可以在O(n2-η2)时间内判定，除非两个自动机的交问题可在O(n2-η1)时间内判定，η10为实数．证明 由定理2的结论和细粒度复杂性理论框架可直接得到．推论1 不存在实数0η1使得有限自动机重置判定问题可以在O(n2-η)时间内判定，除非ETH不成立．证明 由定理3，如果存在实数0η21使得有限自动机重置判定问题可以在O(n2-η2)时间内判定，那么两个自动机的交问题可在O(n2-η1)时间内判定，其中η10为实数．又由引理1，知当k=2时，对于两个有限自动机的交问题，不存在亚二次多项式时间算法，否则ETH不成立．推论1利用两个自动机的交的条件下界证明．实际上，如果两个自动机的交问题存在关于n的亚二次多项式算法，那么利用Rabin-Scott积构造思想，每两两一组重复构造自动机的交，可得k个自动机的交对应存在亚k次算法，其中k2．2.2　道路着色问题下界结论推论2 不存在实数0η21，使得道路着色问题可以在O(n2-η2)时间内判定，除非有限自动机重置判定问题可在O(n2-η1)时间内判定，其中η10为实数．证明思路．有限自动机重置判定问题可看成是对道路着色问题一个候选解的检验．直觉上求解问题至少与验证问题的一个解一样难，比如对于可满足性问题，SAT求解显然不会比验证SAT的一个解简单．文献[9]给出的道路着色问题求解算法将输入的自动机视为一种随机的预备着色方案，若正好是一种可行的着色方案，则说明判定了自动机可重置；否则算法给出其他可行的着色方案．这就意味着可以直接调用道路着色问题的求解算法来判定有限自动机的可重置性，即有限自动机重置问题到道路着色问题存在线性的图灵归约，那么有限自动机重置判定问题的复杂性自然是道路着色问题的复杂性的下界．推论3 不存在实数0η1，使得道路着色问题可以在O(n2-η)时间内判定，除非ETH不成立．由推论1和推论2可证得．由于篇幅所限，推论2和3不再证明．3 影响下界分析的因素3.1　计算模型的选择和影响当在复杂性类P的内部讨论具体问题的时间复杂性函数时，须要更细致分析，不能笼统地用多项式时间表述．算法执行时间与所选择的计算模型密切相关，这不同于对机器模型不敏感的笼统的多项式时间概念要求．比如，在图灵机模型上，k-带图灵机可在O(T(n))时间内求解的问题，其中k≥3，T(n)为k-带图灵机对输入的计算时间，n为输入长度，那么在双带图灵机和单带图灵机上分别需要O(T(n)logn)和O(T(n)2)的执行时间[18]．文献[17]对k个有限自动机交问题的结论证明没有明确指出采用何种计算模型，但可推知采用了更接近现实中计算机的模型——字随机访问模型(word random access machine，WRAM)．首先证明图的三着色问题在ETH下，没有O*(2o(|V|+|E|))时间算法，其中|V|和|E|分别为图的顶点数和边数；然后从三着色问题出发进行归约，给出图的顶点数|V|和边数|E|与自动机个数k、状态数上界n之间满足关系式k=(|V|+|E|)/log3n，从而得到k个有限自动机交问题的条件下界为O*(2logn⋅o(k))．文献[19]的主定理指出，模拟非确定的空间限界的图灵机停机问题(算法)可归约到k个有限自动机的交问题，其中k≥2，该受限图灵机是一个双带二元字母表图灵机．当归约到k个二元字母表的有限自动机的交时，具体对应关系为每个自动机有O(m2|x|σ1+c2σ/k)个状态，其中m为受限图灵机的状态数，x为输入串，σ为二元工作带的空间大小，常数c为特殊分割符#出现的最大次数；进而证明了：如果k个有限自动机交问题可以在no(k)时间内求解，那么NSPACE[n]⊆DTIME[2o(n)]；如果存在实数η0使得k个有限自动机交问题可以在O(nk-η)时间内求解，其中k≥2，那么对于某个δ0实数，有NSPACE[n+o(n)]⊆DTIME[2(1-δ)n]．讨论细粒度归约中问题的算法运行时间和归约本身的运行时间，应该在(或转换到)相同计算模型上讨论．本研究涉及的k个有限自动机的交问题和有限自动机重置判定问题，都是在WRAM模型上讨论的，构造的归约给出了可重置的自动机在状态数、变迁数、字母表大小与两个自动机的大小之间的关系是线性的．3.2　多个有限自动机交的下界对于k个有限自动机交问题，复杂性在一般情况下是PSPACE-完全的．对于这个问题下界的研究较多，较新的文献[19]证明了比文献[16-17]中反驳ETH更强的结论：如果k个有限自动机交问题能够在O(nk-η)时间内求解，其中k≥2，0η1为实数，n为单个自动机的状态数上界，那么深度O(n)、大小为2o(n)且逻辑门的扇入数为2的线路可以在2o(n)时间内求解，这就否定了ETH．因为线性深度且亚指数大小的线路是一种比普通合取范式(CNF)形式受更多约束的计算模型．本研究定理3和推论1说明如果可以在亚二次时间内判定有限自动机的可重置性，那么两个有限自动机的交问题有亚二次时间算法，这就否定了ETH．由定理2，从两个有限自动机的交问题到自动机重置判定问题存在细粒度归约，因此文献[19]中一些更强的结论也适用于自动机重置判定问题，比如，可得到新的非一致线路下界：如果自动机的重置判定算法可以改进到O(n2/(logn)c)，其中c0为任意实数，那么复杂性类NTIME[2O(n)]没有包含在非一致线路类NC1中，这里NC1是深度为O(logn)、大小不超过poly(n)且逻辑门的扇入数为2的线路族的复杂性类．类似地，文献[20]证明了如果ED和LCS问题有亚二次下界，那么复杂性类NTIME[2O(n)]没有包含在非一致线路类NC中．4 结语本研究在ETH下证明了有限自动机重置判定问题和道路着色问题具有关于自动机状态数或图的顶点数的二次多项式时间复杂性下界，均与已有算法的时间复杂度符合．这为阐明已有算法很大程度上就是理论上最好的算法提供了证据．