On small generators (Q802309): Difference between revisions

\textit{C. K. Yap} [Theor. Comput. Sci. 26, 287-300 (1983; Zbl 0541.68017)] has shown that each set having small ''generating'' circuits is in the class NP/Poly which was introduced by \textit{R. M. Karp} and \textit{R. J. Lipton} [Proc. 12th Ann. ACM Symp. Theory of Computing, 302-309 (1980)]. In this paper it is shown that the converse is also true, i.e. each set in NP/Poly has small generators. This settles a question left open by Yap. Further, it is shown that, under certain conditions on C, a set A is in C/Poly if and only if \(A\in C(S)\) for some sparse set S. Specifically, a set has small generators if and only if there is a sparse oracle S with \(A\in NP(S)\).