Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Optimization Problem
Polynomial Time
Subscribe
Academic
Publications
Functions Computable with Nonadaptive Queries to NP
Functions Computable with Nonadaptive Queries to NP,10.1007/s002240000079,Theory of Computing Systems / Mathematical Systems Theory,Harry Buhrman,Jim
Edit
Functions Computable with Nonadaptive Queries to NP
(
Citations: 9
)
BibTex

RIS

RefWorks
Download
Harry Buhrman
,
Jim Kadin
,
Thomas Thierauf
. We study FP NP , the class of functions that can be computed in
polynomial time
with nonadaptive queries to an NP oracle. This is motivated by the question of whether it is possible to compute witnesses for NP sets within FP NP . The known algorithms for this task all require sequential access to the oracle. On the other hand, there is no evidence known yet that this should not be possible with parallel queries. We define a class of optimization problems based on NP sets, where the optimum is taken over a polynomially bounded range (NPbOpt). We show that if such an
optimization problem
is based on one of the known NPcomplete sets, then it is hard for FP NP . Moreover, we characterize FP NP as the class of functions that reduces to such optimization functions. We call this property strong hardness. The main question is whether these function classes are complete for FP NP . That is, whether it is possible to compute an optimal value for a given
optimization problem
in FP NP . We show that these optimization problems are complete for FP NP , if and only if one can compute membership proofs for NP sets in FP NP . This indicates that the completeness question is a hard one.
Journal:
Theory of Computing Systems / Mathematical Systems Theory  MST
, vol. 31, no. 1, pp. 7792, 1998
DOI:
10.1007/s002240000079
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
www.springerlink.com
)
(
www.springerlink.com
)
More »
Citation Context
(2)
...One can for the same reason strengthen to a PH = SNP∩coNP 2 conclusion a closely related theorem, namely, the result of Buhrman, Kadin, and Thierauf [
BKT98
] that if, in a certain model of access to partial functions, the solution function of some “universal relation [AB92]” is computable in the class “FPNPSV[1],” then PH = NPNP...
Jinyi Cai
,
et al.
Competing Provers Yield Improved KarpLipton Collapse Results
... In fact, it is at least plausible to conjecture that NPcomplete sets may have even more in common than mere isomorphism (and, indeed, many natural sets do have more in common), and many papers have wondered just what that “more” may be. One could say that this general type of intuition has led people to such notions as structurepreserving reductions [LL78,ADP80], witnessisomorphic reductions [FHT97], universal relations [AB92,Bis95,
...
Unknown.
Takehome complexity
References
(17)
A Taxonomy of Complexity Classes of Functions
(
Citations: 114
)
Alan L. Selman
Journal:
Journal of Computer and System Sciences  JCSS
, vol. 48, no. 2, pp. 357381, 1994
Quantitative Relativizations of Complexity Classes
(
Citations: 118
)
Timothy J. Long
,
Alan L. Selman
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 13, no. 3, pp. 461487, 1984
Structural Analysis of the Complexity of Inverse Functions
(
Citations: 17
)
Osamu Watanabe
,
Seinosuke Toda
Journal:
Theory of Computing Systems / Mathematical Systems Theory  MST
, vol. 26, no. 2, pp. 203214, 1993
Complexity Measures for PublicKey Cryptosystems
(
Citations: 224
)
Joachim Grollmann
,
Alan L. Selman
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 17, no. 2, pp. 309335, 1988
Functions Computable with Limited Access to NP
(
Citations: 21
)
Mitsunori Ogihara
Journal:
Information Processing Letters  IPL
, vol. 58, no. 1, pp. 3538, 1996
Sort by:
Citations
(9)
Weighted argument systems: Basic definitions, algorithms, and complexity results
(
Citations: 4
)
Paul E. Dunne
,
Anthony Hunter
,
Peter McBurney
,
Simon Parsons
,
Michael Wooldridge
Journal:
Artificial Intelligence  AI
, vol. 175, no. 2, pp. 457486, 2011
The computational complexity of ideal semantics
(
Citations: 10
)
Paul E. Dunne
Journal:
Artificial Intelligence  AI
, vol. 173, no. 18, pp. 15591591, 2009
Universal relations and #Pcompleteness
Hervé Fournier
,
Guillaume Malod
Journal:
Theoretical Computer Science  TCS
, vol. 407, no. 13, pp. 97109, 2008
The consequences of eliminating NP solutions
Piotr Faliszewski
Journal:
Computer Science Review
, vol. 2, no. 1, pp. 4054, 2008
Universal Relations and #PCompleteness
Hervé Fournier
,
Guillaume Malod
Conference:
Italian Conference on Algorithms and Complexity  CIAC
, pp. 368379, 2006