论文标题
计算复杂性类的逻辑表征
Logical characterizations of computational complexity classes
论文作者
论文摘要
描述性复杂性理论是计算复杂性研究的重要领域。在这个方向上，可以仅通过逻辑方法描述组合问题，而无需诉诸复杂算法。美国数学家法金（Fagin）于1974年撰写了这项方向的第一部作品。本文描述了描述性复杂性理论方法的发展。
Descriptive complexity theory is an important area in the study of computational complexity. In this direction, it is possible to describe combinatorial problems exclusively by logical methods, without resorting to the use of complicated algorithms. The first work in this direction was written in 1974 by the American mathematician Fagin. The article describes the development of methods of the theory of descriptive complexity.
