文章基本信息

标题：Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy
本地全文：下载
作者：Peter Bro Miltersen ; Vinodchandran N. Variyam ; Osamu Watanabe 等
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：1999
卷号：6
期号：46
出版社：Aarhus University
摘要：Lower bounds on circuit size were previously established for functions in Sigma^p_2, ZPP^NP, Sigma^exp_2, ZPEXP^NP and MA_exp. We investigate the general question: Given a time bound f(n). What is the best circuit size lower bound that can be shown for the classes MA-TIME[f], ZP-TIME^NP[f], . . . using the techniques currently known? For the classes MA_exp, ZPEXP^NP, and Sigma^exp_2 , the answer we get is "half-exponential". Informally, a function f is said to be half-exponential if f composed with itself is exponential