ON APPROXIMATION ALGORITHMS FOR =P

作     者：STOCKMEYER, L 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1985年第14卷第4期

页      面：849-861页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：#P approximation algorithms probabilistic algorithms computational complexity relativization 

摘      要：The theme of this paper is to investigate to what extent approximation, possibly together with randomization, can reduce the complexity of problems in Valiant’s class # P. In general, any function in # P can be approximated to within any constant factor by a function in the class 3p role=presentationΔp3span style=display: inline-