commit bfe1ffd913565cca2212ad7721d15c8457d20ffa parent a692ba6dc77b6c5c20e6461f570e6dd9ca60c417 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Sun, 22 Jun 2025 14:07:10 +0200 commit with codex Diffstat:
| circuit_bounds_vs_complexity_bounds | | | 11 | +++++++++++ |
1 file changed, 11 insertions(+), 0 deletions(-)
diff --git a/circuit_bounds_vs_complexity_bounds b/circuit_bounds_vs_complexity_bounds @@ -0,0 +1,11 @@ +# Circuit bounds vs complexity bounds + +Two different things: + +- [circuit] [lower_bounds]: + - typically unconditional + - less fragile wrt the underlying [computational_model] + - only gives bounds on algorithms whose [trace] can be expressed in this [circuit_class] +- [computational_complexity] [lower_bounds]: typically conditional + +Up: [knowledge_compilation]