The Minimum Oracle Circuit Size Problem

The Minimum Oracle Circuit Size Problem

We consider variants of the minimum circuit size problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MSCP[superscript QBF] is known to be complete for PSPACE under ZPP reductions. We show that it is not com...

Full description

Bibliographic Details
Main Authors: Allender, Eric, Holden, Dhiraj, Kabanets, Valentine
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:English
Published: Springer International Publishing 2017
Online Access:http://hdl.handle.net/1721.1/106913

Internet

http://hdl.handle.net/1721.1/106913

Similar Items