Symmetric Exponential Time Requires Near-Maximum Circuit Size
Lijie Chen, Shuichi Hirahara, Hanlin Ren
Abstract
We show that there is a language in S2E/1 (symmetric exponential time with one bit of advice) with circuit complexity at least 2n/n. In particular, the above also implies the same near-maximum circuit lower bounds for the classes Σ2E, (Σ2E∩Π2E)/1, and ZPENP/1. Previously, only ”half-exponential” circuit lower bounds for these complexity classes were known, and the smallest complexity class known to require exponential circuit complexity was Δ3E = EΣ2P (Miltersen, Vinodchandran, and Watanabe COCOON’99).
Topics & Concepts
Exponential functionCircuit complexityComputational complexity theoryExponential growthTime complexityComplexity classMathematicsClass (philosophy)Upper and lower boundsComputer scienceCombinatoricsDiscrete mathematicsElectronic circuitAlgorithmMathematical analysisPhysicsQuantum mechanicsArtificial intelligenceComplexity and Algorithms in GraphsCryptography and Data SecurityOptimization and Search Problems