wiki_research

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

minimum_circuit_size_problem (400B)

      1 # Minimum circuit size problem (MCSP)
      2 
      3 Given the truth table of a [boolean_formula] and an integer s, decide if there is a [boolean_circuit] of size s computing the formula
      4 
      5 Clearly in [nptime] and not known to be [np_hard], cf [ilango2022minimum]
      6 
      7 [minimum_circuit_size_problem_arithmetic_circuit]
      8 
      9 See also: [minimum_formula_size_problem], [addition_chain]
     10 
     11 Up: [minimization] of [boolean_circuit]