package Ġmath Ċ Ċ import Ġutil . One Array Ċ import Ġutil . one ArrayOf Ċ Ċ // Ġgiven Ġa ĠDis j unct ive ĠNormal ĠForm Ġ( DN F ), Ġi . e . ĠOR ing Ġseveral Ġconjunction s , Ġex . Ċ // Ġ(! x Ġ& Ġy Ġ& Ġ! z ) Ġ| Ġ( y Ġ& Ġz ) Ġ| Ġ( x Ġ& Ġ! y Ġ& Ġ! z ), Ġdetermine Ġif Ġit Ġis ĠS AT is f iable , Ġi . e . Ċ // Ġfind Ġthere Ġexists Ġx , Ġy , Ġz ,... Ġ: ĠD NF Ġcan Ġoutput Ġtrue Ġin Ġpolynomial Ġtime Ċ Ċ fun Ġmain ( args : ĠArray < String >) Ġ{ Ċ ĉ // Ġfrom Ġthe Ġexample Ġabove Ċ ĉ val ĠD NF Ġ= Ġone ArrayOf ( Ċĉĉ ĉ one ArrayOf (" ! x ", Ġ" y ", Ġ"! z "), Ċĉĉ ĉ one ArrayOf (" y ", Ġ" z "), Ċĉĉ ĉ one ArrayOf (" x ", Ġ"! y ", Ġ"! z ")) ĊĊ ĉ println ( DN F . sat ()) Ċ } Ċ Ċ fun ĠOne Array < One Array < String >> . sat () Ġ= Ġany Ġ{ Ġ! it . contains Conflict () Ġ} Ċ Ċ fun ĠOne Array < String >. contains Conflict (): ĠBoolean Ġ{ Ċ ĉ val Ġ( t , Ġf ) Ġ= Ġas Sequence (). partition Ġ{ Ġit [ 0 ] Ġ!= Ġ' !' Ġ} Ċ ĉ return Ġf . any Ġ{ Ġt . contains ( it . substring ( 1 )) Ġ} Ċ } Ċ Ċ // Ġnote Ġthat Ġthis Ġis Ġnot ĠCon j unct ive ĠNormal ĠForm Ġ( CN F ) Ġwhich Ġis ĠNP - hard Ċ // Ġgoogle Ġrelated Ġtopics Ġfor Ġmore Ġinfo