BOUNDED QUERY CLASSES

作     者：WAGNER, KW 

作者机构：Univ Wuerzburg Wuerzburg Germany 

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

年 卷 期：1990年第19卷第5期

页      面：833-846页

核心收录：

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

主　　题：68Q15 polynomial time oracle machines number of oracle queries truth-table reducibility Boolean hierarchy 

摘      要：Polynomial time machines having restricted access to an NP oracle are investigated. Restricted access means that the number of queries to the oracle is restricted or the way in which the queries are made is restricted (e.g., queries made during truth-table reductions). Very different kinds of such restrictions result in the same or comparable complexity classes. In particular, the class PNP[O(logn)] role=presentationPspan class=te