Completeness and weak completeness under polynomial-size circuits

DOI10.1006/INCO.1996.0017zbMath0853.68098OpenAlexW2029295554MaRDI QIDQ1917077

Jack H. Lutz, David W. Juedes

Publication date: 2 January 1997

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1996.0017

zbMATH Keywords

nonuniform complexity of problemsweakly P/Poly-Turing-complete problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Scaled dimension and nonuniform complexity ⋮ Scaled dimension and the Kolmogorov complexity of Turing-hard sets

This page was built for publication: Completeness and weak completeness under polynomial-size circuits