Threshold Behavior in a Boolean Network Model for SAT.

摘要: Boolean satisfiability (SAT) is the canonical NP-complete problem that plays an important role in AI and has many practical applications Computer Science general. networks (BN) are dynamical systems have recently been proposed as algorithm for solving SAT problems [7]. We carried out a detailed investigation of properties BN corresponding to random different size. varied size by changing number variables clauses formula. show dynamics 3-SAT display threshold-like behavior, although this transition occurs far below well known phase computational complexity 3-SAT. This threshold behavior does not appear be connected between frozen chaotic regimes BN.