| 完全二叉树理论的计算复杂度 |
| |
| 引用本文： | 李志敏,罗里波,李祥.完全二叉树理论的计算复杂度[J].数学学报,2008,51(2):311-318. |
| |
| 作者姓名： | 李志敏 罗里波 李祥 |
| |
| 作者单位： | 贵州大学计算机软件与理论研究所,贵州民族学院数学与计算机科学学院,贵州大学计算机软件与理论研究所 贵阳 550025 贵州民族学院数学与计算机科学学院 贵阳 550025 孝感学院计算机科学系 孝感 432000,贵阳 550025 北京师范大学数理学院 北京 100875,贵阳 550025 |
| |
| 摘 要： | 完全二叉树的一阶理论已被证明具有量词消去的性质,进而计算了完全二叉树模型中元素的CB秩.本文利用有界Ehrenfeucht-Frassé博弈研究完全二叉树的一阶理论,证明了此理论的时间计算复杂度上界为22cn,空间计算复杂度上界为2dn(其中n为输入长度,c,d为合适的常数).
|
| 关 键 词： | 完全二叉树的一阶理论 有界Ehrenfeucht-Frassé博弈 计算复杂度 |
| 文章编号： | 0583-1431（2008）02-0311-08 |
On the Computational Complexity of the Theory of Complete Binary Trees |
| |
| Abstract: | 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-Frassé game, we demonstrate that the first-order theory of a complete binary tree can be decided within linear double exponential Turing time 22cn and Turing space 2cn (n is the length of input, c and d are suitable constants). |
| |
| Keywords: | first-order theory of a complete binary tree bounded Ehrenfeucht-Frassé game upper bounds for computational complexity |
|
| 点击此处可从《数学学报》浏览原始摘要信息 |
| 点击此处可从《数学学报》下载免费的PDF全文 |
|
