Descriptive Complexity of #P Functions
Descriptive Complexity of #P Functions
复制标题
描述的复杂性
DOI：
10.1006/jcss.1995.1039
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Madhukar N. Thakur
中科院分区：
文献类型：
--
作者：
Sanjeev Saluja;K. Subrahmanyam;Madhukar N. Thakur
Please try later.
We give a logic-based framework for defining counting problems and show that it exactly captures the problems in Valiant?s counting class #P. We study the expressive power of the framework under natural syntactic restrictions and show that some of the subclasses obtained in this way contain problems in #P with interesting computational properties. In particular, using syntactic conditions, we isolate a class of polynomial time computable #P problems and, also, a class in which every problem is approximable by a polynomial time randomized algorithm. These results set the foundation for further study of the descriptive complexity of the class #P. In contrast, we show, under reasonable complexity theoretic assumptions, that it is an undecidable problem to tell if a counting problem expressed in our framework is polynomial time computable or if it is approximable by a randomized polynomial time algorithm. Finally, we discuss some open problems which arise naturally from this work.