wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

circuit_bounds_vs_complexity_bounds (363B)

      1 # Circuit bounds vs complexity bounds
      2 
      3 Two different things:
      4 
      5 - [circuit] [lower_bounds]:
      6   - typically unconditional
      7   - less fragile wrt the underlying [computational_model]
      8   - only gives bounds on algorithms whose [trace] can be expressed in this [circuit_class]
      9 - [computational_complexity] [lower_bounds]: typically conditional
     10 
     11 Up: [knowledge_compilation]