wiki_research

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

minimum_equivalent_dnf (585B)

      1 # Minimum equivalent DNF
      2 
      3 Given a [DNF] φ and integer k, does there exist a [DNF] which is [equivalent] to φ and has at most k [literal] occurrences?
      4 
      5 Studied in [umans2001minimum], showed to be [Sigma_P_2_complete]
      6 
      7 Generalization to arbitrary [Boolean_formulas] (and also to bounded-depth [Boolean_formulas] with other depth bounds): [MEE]
      8 
      9 Related problem via [truth_tables] on [Boolean_formulas] ([Minimum_formula_size_problem]) and [Boolean_circuits] ([MCSP])
     10 
     11 See also: [umans2001minimum], [DNF_minimization], [goldsmith2008complexity]
     12 
     13 Up: [minimum_equivalent_problem], [DNF]