完全二叉树理论的计算复杂度

On the Computational Complexity of the Theory of Complete Binary Trees

完全二叉树的一阶理论已被证明具有量词消去的性质,进而计算了完全二叉树模型中元素的CB秩.本文利用有界Ehrenfeucht-Frassé博弈研究完全二叉树的一阶理论,证明了此理论的时间计算复杂度上界为22cn,空间计算复杂度上界为2dn(其中n为输入长度,c,d为合适的常数).

The first-order theory of a complete binary tree is decidable by the quantifier elimination, we also know the CB rank of elements of a complete binary tree. In this paper, by using the bounded Ehrenfeucht-Fraissé game, we demonstrate that the first-order theory of a complete binary tree can be decided within linear double exponential Turing time 2^2cn and Turing space 2^cn （n is the length of input, c and d are suitable constants）.