Answers.Body: <p>It's not completely clear from your question, but it looks like you want to prove that exact inference in a Bayesian Network is both NP-Hard and P-Hard.</p>
  
  <p>It appears that you have proven that it is NP-Hard, but are unsure how to show that it is also P-Hard. </p>
  
  <p>This is more of a TCS question than an AI question, but shouldn't be too difficult. You just need to pick a P-Complete problem and reduce it to BN. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-07-16T19:02:42.960Z
Answers.LastActivityDate: 2018-07-16T19:20:37.360Z
Answers.LastEditDate: 2018-07-16T19:20:37.360Z
Answers.UserDisplayName: John Doucette
Body: <p>I should show that exact inference in a Bayesian network (BN) is NP-hard and P-hard by using a 3-SAT problem.</p>
  
  <p>So, I did formulate a 3-SAT problem by defining 3-CNF:</p>
  
  <p><span class="math-container">$$(x_1 \lor x_2) \land (\neg x_3 \lor x_2) \land (x_3 \lor x_1)$$</span></p>
  
  <p>I reduced it to inference in a Bayesian network, and produced all conditional probabilities, and I know which variable assignment would lead for the entire expression to be true.</p>
  
  <p>I am aware of the difference between P and NP. (Please correct me if I am wrong):</p>
  
  <p>Any P problem with an input of the size <span class="math-container">$n$</span> can be solved in <span class="math-container">$\mathcal{O}(n^c)$</span>. For NP, the polynomial-time cannot be determined, hence, nondeterministic polynomial time. The question that scientists try to answer is whether a computer who is able to verify a solution would also be able to find a solution. P= NP?</p>
  
  <p>However, I am still not sure how I can prove that exact inference in Bayesian network is NP-hard and P-hard.</p>
  
Tags: <proofs><time-complexity><bayesian-networks><computational-complexity><inference>
Title: Why is exact inference in a Bayesian network both NP-hard and P-hard?
UserDisplayName: xava
ThreadText: # Why is exact inference in a Bayesian network both NP-hard and P-hard?
  
  (Asked by: username_0 on 2018-07-05)
  
  I should show that exact inference in a Bayesian network (BN) is NP-hard and P-hard by using a 3-SAT problem.
  
  So, I did formulate a 3-SAT problem by defining 3-CNF:
  
  $$(x\_1 \lor x\_2) \land (\neg x\_3 \lor x\_2) \land (x\_3 \lor x\_1)$$
  
  I reduced it to inference in a Bayesian network, and produced all conditional probabilities, and I know which variable assignment would lead for the entire expression to be true.
  
  I am aware of the difference between P and NP. (Please correct me if I am wrong):
  
  Any P problem with an input of the size $n$ can be solved in $\mathcal{O}(n^c)$. For NP, the polynomial-time cannot be determined, hence, nondeterministic polynomial time. The question that scientists try to answer is whether a computer who is able to verify a solution would also be able to find a solution. P= NP?
  
  However, I am still not sure how I can prove that exact inference in Bayesian network is NP-hard and P-hard.
  
  **Tags:** proofs, time-complexity, bayesian-networks, computational-complexity, inference
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-07-16. Score: 1
  
  It's not completely clear from your question, but it looks like you want to prove that exact inference in a Bayesian Network is both NP-Hard and P-Hard.
  
  It appears that you have proven that it is NP-Hard, but are unsure how to show that it is also P-Hard.
  
  This is more of a TCS question than an AI question, but shouldn't be too difficult. You just need to pick a P-Complete problem and reduce it to BN.
  
  
  ---
  
  