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.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.
