返回Google圖書搜尋

Advice from Nonadaptive Queries to NP.

University of Rochester. Department of Computer ScienceYenjo HanThomas Thierauf

出版	University of Rochester [Department of] Computer Science, 1993
URL	http://books.google.com.hk/books?id=g08yHQAACAAJ&hl=&source=gbs_api

註釋Abstract: "Consider the standard model of computation to decide a language that is bounded truth-table reducible to an NP set: on a given input, a polynomial-time Turing machine, called a generator, produces a constant number of queries to the NP oracle; then, a second polynomial-time Turing machine, called an evaluator, given the answers to the queries, determines the membership of the given input. In this paper, we investigate the classes of languages that are decided by bounded truth- table reductions to an NP set in which evaluators do not have full access to the answers to the queries but get only partial information such as the number of queries that are in the oracle set or even just this number modulo some constant