NDLI: Adaptive versus nonadaptive queries to NP and p-selective sets

Please wait, while we are loading the content...

Computational complexity : Volume 26

Computational complexity : Volume 25

Computational complexity : Volume 24

Computational complexity : Volume 23

Computational complexity : Volume 22

Computational complexity : Volume 21

Computational complexity : Volume 20

Computational complexity : Volume 19

Computational complexity : Volume 18

Computational complexity : Volume 17

Computational complexity : Volume 16

Computational complexity : Volume 15

Computational complexity : Volume 14

Computational complexity : Volume 13

Computational complexity : Volume 12

Computational complexity : Volume 11

Computational complexity : Volume 10

Computational complexity : Volume 9

Computational complexity : Volume 8

Computational complexity : Volume 8, Issue 4, December 1999

Computational complexity : Volume 8, Issue 3, December 1999

Computational complexity : Volume 8, Issue 2, November 1999

The complexity of matrix rank and feasible systems of linear equations

Lower bounds for the polynomial calculus and the Gröbner basis algorithm

Randomness complexity of private computation

Adaptive versus nonadaptive queries to NP and p-selective sets

Feasibly continuous type-two functionals

Computational complexity : Volume 8, Issue 1, June 1999

Computational complexity : Volume 7

Adaptive versus nonadaptive queries to NP and p-selective sets

Content Provider	Springer Nature Link
Author	Naik, A.V. Selman, A.L.
Copyright Year	1998
Abstract	We prove that P = NP follows if for some $ k > 0 $ , the class $ {\rm PF}^{\rm NP}_{tt} $ of functions that are computable in polynomial time by nonadaptively accessing an oracle in NP is effectively included in PFNP[k⌈log n⌉— 1], the class of functions that are computable in polynomial k⌈log n⌉— 1 queries to an oracle in NP.¶We draw several observations and relationships between the following two properties of a complexity class $ \cal C $ : whether there exists a truthtable hard p-selective language for $ \cal C $ , and whether polynomially-many nonadaptive queries to $ \cal C $ can be answered by making O(log n)-many adaptive queries to $ \cal C $ (in symbols, whether $ {\rm PF}^{\cal C}_{tt} \subseteq {\rm PF}^{\cal C}[O({\rm log}\,n)] $ ). Among these, we show that if there exists an NP-hard p-selective set under truth-table reductions, then $ {\rm PF}^{\rm NP}_{tt} \subseteq {\rm PF}^{\rm NP}[O({\log}\,n)] $ . However, if $ {\cal C} \supseteq {\rm ZPP}^{\rm NP} $ , then these two properties are equivalent.
Starting Page	169
Ending Page	187
Page Count	19
File Format	PDF
ISSN	10163328
Journal	Computational complexity
Volume Number	8
Issue Number	2
e-ISSN	14208954
Language	English
Publisher	Birkhäuser Verlag
Publisher Date	1999-11-01
Publisher Place	Basel
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On P versus NP $ \cap $ co-NP for decision trees and read-once branching programs

A non-canonical example to support P is not equal to NP

Inverse NP Problems

Regular Queries on Graph Databases

Learning Sets of Antecedent-restricted Functional and Multivalued Dependencies with Queries

The Minimum Oracle Circuit Size Problem

A note on closeness betweenNP-hard sets andC=P

Genetic-fuzzy approach to the Boolean satisfiability problem

Optimal Broadcasting Strategies for Conjunctive Queries over Distributed Data

Adaptive versus nonadaptive queries to NP and p-selective sets

Similar Documents

On P versus NP $ \cap $ co-NP for decision trees and read-once branching programs

A non-canonical example to support P is not equal to NP

Inverse NP Problems

Regular Queries on Graph Databases

Learning Sets of Antecedent-restricted Functional and Multivalued Dependencies with Queries

The Minimum Oracle Circuit Size Problem

A note on closeness betweenNP-hard sets andC=P

Genetic-fuzzy approach to the Boolean satisfiability problem

Optimal Broadcasting Strategies for Conjunctive Queries over Distributed Data

Adaptive versus nonadaptive queries to NP and p-selective sets