资源分类
》 资源 》论文》Probabilistic Satis?ability: Logic-Based Algorithms and Phase Transition?

Probabilistic Satis?ability: Logic-Based Algorithms and Phase Transition?

2019-11-12 | |  48 |   38 |   0
Abstract In this paper, we study algorithms for probabilistic satis?ability (PSAT), an NP-complete problem, and their empiric complexity distribution. We de?ne a PSAT normal form, based on which we propose two logic-based algorithms: a reduction of normal form PSAT instances to SAT, and a linearalgebraic algorithm with a logic-based column generation strategy. We conclude that both algorithms present a phase transition behaviour and that the latter has a much better performance.

上一篇：Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable

下一篇：Using Payoff-Similarity to Speed Up Search Timothy Furtak and Michael Buro

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to learn...

    The move from hand-designed features to learned...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...