commit de8f8acc0ec2f8f5fa77a7efd7be1cbfc13071b9 parent 210f42c13d242b3ace103d2439f6965f36c0e1d5 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]