出版社：The Editorial Committee of the Interdisciplinary Information Sciences
摘要：Proving circuit lower bounds in uniform classes is one of the grand challenges in computational complexity theory. Particularly, it is well known that proving superpolynomial circuit lower bounds in NP resolves the longstanding conjecture NP≠P. Towards the final goal, a lot of work have been dedicated to approaches proving circuit lower bounds in high classes. This tutorial article overviews those proof techniques developed for circuit lower bounds in higher classes than NP such as PH, ZPPNP, MAEXP, PP, Promise-MA, NEXP, and so forth.
关键词：circuits;computational complexity;lower bounds;NP versus P conjecture;high uniform classes
