3 ms·
Exact inference in Bayesian networks is known to be NP-hard (see http://www2.stat.duke.edu/~sayan/npcomplete.pdf http://www2.stat.duke.edu/~sayan/npcomplete.pdf
by jcranmer 10y ago
Exact inference in Bayesian networks is known to be NP-hard (see http://www2.stat.duke.edu/~sayan/npcomplete.pdf http://www2.stat.duke.edu/~sayan/npcomplete.pdf) (apparently, it's actually #P-hard). I'm not sure inference in Bayesian networks is in BPP in the first place, so the claim that this is grounds to prove BPP=BQP is pretty unlikely.