wiki_research

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

minimum_formula_size_problem (568B)

      1 # Minimum formula size problem (MFSP)
      2 
      3 Given the explicit [truth_table] of a [Boolean_function], and a positive integer s, determine if there is an equivalent [Boolean_formula] (over the [de_Morgan_basis], i.e., with [AND] and [OR] and [NOT] gates) with at most s leaves
      4 
      5 Not in [PTIME] under [exponential_time_hypothesis], cf [ilango2022minimum]
      6 
      7 Notion of a [search_to_decision_reduction]
      8 
      9 See also: [minimum_circuit_size_problem], [umans2001minimum], [minimum_equivalent_DNF], [Minimum_equivalent_expression]
     10 
     11 Up: [minimization] of [formula_boolean]
     12 
     13 Aliases: MFSP