This paper investigates the computational complexity of the optimal de Finetti’s coherence criterion within the framework of Łukasiewicz logic. We prove that the Weighted Decision Coherence problem is NP-complete, the Weighted Optimal Coherence problem is FPNP-complete, and the unweighted Optimal Coherence problem is FPNP[log(n)]-complete. These results are obtained by establishing a correspondence between coherence in Łukasiewicz logic and reductions to the logic of equational states expanded with truth-constants.
Optimizing de Finetti’s Coherence: A Complexity Analysis
Lapenta, Serafina;Napolitano, Sebastiano
2026
Abstract
This paper investigates the computational complexity of the optimal de Finetti’s coherence criterion within the framework of Łukasiewicz logic. We prove that the Weighted Decision Coherence problem is NP-complete, the Weighted Optimal Coherence problem is FPNP-complete, and the unweighted Optimal Coherence problem is FPNP[log(n)]-complete. These results are obtained by establishing a correspondence between coherence in Łukasiewicz logic and reductions to the logic of equational states expanded with truth-constants.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
