The computational decision problem CPA is a variant of the probabilitistic satisfiability problem PSAT. In this paper we investigate the behavior of an algorithm which decides CPA applied to the still NP-complete subproblem 2CPA, whose instances have at most two literals per clause. We locate, as it is done for some satisfiability problems, a critical value for the ratio alpha=m/n, where m is the number of binary clauses present in the instance and n is the number of events. This point divides ``almost all coherent'' instances from ``almost all not coherent''; moreover the most difficult instances lies near this point.

An Empirical Complexity Study for a 2CPA Solver

BAIOLETTI, Marco;CAPOTORTI, Andrea;TULIPANI, Sauro
2006

Abstract

The computational decision problem CPA is a variant of the probabilitistic satisfiability problem PSAT. In this paper we investigate the behavior of an algorithm which decides CPA applied to the still NP-complete subproblem 2CPA, whose instances have at most two literals per clause. We locate, as it is done for some satisfiability problems, a critical value for the ratio alpha=m/n, where m is the number of binary clauses present in the instance and n is the number of events. This point divides ``almost all coherent'' instances from ``almost all not coherent''; moreover the most difficult instances lies near this point.
2006
9780444520753
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/153838
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact