Functions computable with limited access to NP

Mitsunori Ogihara

doi:10.1016/0020-0190(96)00030-0

Back

Functions computable with limited access to NP

Journal article

Peer reviewed

Functions computable with limited access to NP

Mitsunori Ogihara

Information processing letters, Vol.58(1), pp.35-38

1996

DOI: https://doi.org/10.1016/0020-0190(96)00030-0

Abstract

Computational complexity

Nondeterministic functions

Polynomial hierarchy

Reducibility

It is shown for any constant c < 1 that NP multi-valued functions do not have refinements computable in polynomial time with c log n functional oracle queries to single-valued NP functions unless the polynomial-time hierarchy collapses to its second level.

Metrics

5 Record Views

12 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Citation topics: 4 Electrical Engineering, Electronics & Computer Science; 4.182 Data Structures, Algorithms & Complexity; 4.182.1226 Computability
Web Of Science research areas: Computer Science, Information Systems
ESI research areas: Computer Science

UN Sustainable Development Goals (SDGs)

This output has contributed to the advancement of the following goals:

Source: InCites

Details

Title: Functions computable with limited access to NP
Creators: Mitsunori Ogihara - Department of Computer Science, University of Rochester, Rochester, NY 14627, USA
Publication Details: Information processing letters, Vol.58(1), pp.35-38
Publisher: Elsevier B.V
Academic Unit: College of A&S; A&S - Computer Science
Language: English
Resource Type: Journal article
Record Identifier: 991031615430402976