wiki_research

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

addition_chain (350B)

      1 # Addition chain
      2 
      3 https://en.wikipedia.org/wiki/Addition_chain
      4 
      5 It is not known to be [NP_hard]
      6 - cf https://math.stackexchange.com/a/109905
      7 - however the [addition_sequence] problem is [NP_hard]
      8 
      9 Variant: [addition_subtraction_chain]
     10 
     11 See also: [minimum_circuit_size_problem], [carry], [Smallest_grammar_problem]
     12 
     13 Up: [theoretical_computer_science]