Bøger af Jayashree Veerendra Katti

Boolean Satisfiability (SAT)is one of the famous problem present in the field of computer scienceand mathematical theory. Boolean Satisfiability can be defined as the problem of finding assignmentsto the variables such that, it satisfy the given a Boolean formula. Boolean Satisfiabilityproblems arise in many applications such as cryptology, hardware and software verification,reliability, artificial intelligence, decision under logic constraints, computational studies of Biologicalnetworks. Recent application of solving Boolean systems arises in Biological(Genetic Regulatory) Networks.The CNF Satisfiability(CNFSAT) Problem is one of the important case of of the SatisfiabilityProblem, where the Boolean formula is represented in the CNF form i.e.Conjunctive NormalForm (CNF).This means Boolean formula is a conjunction of clauses and each clause is a disjunctionof literals. A literal is a variable or its negation.CNF SAT has central importance incomputer science. SAT normally suits to the formulas if they are in Conjunctive NormalForm , as mentioned, should be a set of clauses.SAT is considered as NP-complete problem in its general form. Inspite of this reality,there are number of problems which can be successfully solved by SAT such as cryptanalysis,bioinformatics, hardware verification, etc. For recent past twenty years the effectiveness ofSAT algorithms has significantly increased. XOR-SAT is one special case of Boolean SAT where each equation is an exclusive OR(XOR) combination of variables. Such linear XOR systems naturally appear in problems suchas quadratic sieve method for prime factorization of numbers. Also in decoding of linearerror correction coding, linear XOR systems.In the specific case of cryptography, SAT solversbecame a very important tool to analyse and break encoding mechanisms. Within the case ofcryptanalytic application, many times SAT solvers have faced with issues that encode relativelylarge amount of XOR constraints.