Relative to a random oracle, co-NP [not equal to or included in] IP/poly

The main result in this paper is that if IP is further given polynomial-length advice along with the random oracle R, it still does not include all of co-NPᴿ. In this case, intuition says that since co-NP is uniform, adding nonuniformity to IPᴿ won't be of any help. On the other hand, IP accomplishes surprising things with few resources, and advice is an additional non-trivial resource.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science

Year dc:date.issued

1993

Author dc:creator

• Reynolds, Owen P.

Language dc:language.iso

en

Repository record dc:identifier.uri

https://dr.lib.iastate.edu/handle/20.500.12876/jw27nQqv

OAI identifier oai:identifier

oai:dr.lib.iastate.edu:20.500.12876/jw27nQqv