在有序结构上刻画βP的逻辑CSSCI

我们在膨胀不动点逻辑IFP的基础上,加入一种带有(多重)对数上界的新二阶量词,并且证明了,在有序结构上我们的新逻辑■logωIFP刻画受限非确定性复杂类βP。为了研究该逻辑的表达力,我们也设计了一种新的Ehrenfeucht-Fraïssé博弈,并说明在最一般的情况下,也就是在全体有穷模型之上,该逻辑对βP的刻画并不成立。