wiki_research

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

mpe (465B)

      1 # Most Probable Explanation (MPE)
      2 
      3 find [satisfying_valuation] with largest weight for a [boolean_function]
      4 
      5 - for [monotone2cnf]: [np_hard] by reduction from [minimum_vertex_cover]
      6 - for [horn_clause]: [np_hard] by padding previous argument
      7 - for [2horn_clause] (no two literals of same polarity per clause = "definite horn with size at most two), [ptime] by reduction to [project_selection_problem]
      8 
      9 Up: [satisfiability_boolean]
     10 
     11 See also: [sharp_satisfiability]