Correction to: Parameterized Complexity of Dynamic Belief Updates: A Complete Map
Journal of Logic and Computation · 2024
This article investigates the computational complexity of 14 problems, and provided proofs that 12 of these were fixed-parameter intractable (FP-intractable), while the remaining 2 were fixedparameter tractable (FP-tractable).However, after publication, authors discovered an error in the proof of Theorem 3 (whose result was that the problem acopu-DBU was FP-intractable).Further investigation showed that the proof could be easily fixed, but Theorem 3 had to be slightly modified (by removing parameter o).In the correction, Theorem 3 thus shows a different result, but its corollaries are left untouched.In consequence, the complexity of acopu-DBU was left as unsettled.However, a very minor adaptation of Theorem 4 (and some lemmas it depends on) was enough to show that acopu-DBU is actually FP-tractable, thus settling the complexity of every problem studied, as previously.The end results are then changed, as one problem thought to be FP-intractable is FP-tractable.The article has been emended to show the correct results, using the proofs found in the original version of the paper, which have only been very slightly revised.The originally published article has had the following changes made.