New non-uniform lower bounds for uniform classes
From MaRDI portal
Publication:5368753
DOI10.4230/LIPIcs.CCC.2016.19zbMath1380.68196OpenAlexW2465024128MaRDI QIDQ5368753
Rahul Santhanam, Lance J. Fortnow
Publication date: 10 October 2017
Full work available at URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.19
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (4)
Effective guessing has unlikely consequences ⋮ Complexity with Rod ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly
This page was built for publication: New non-uniform lower bounds for uniform classes
