In the theory of computation, decision problems are divided into two different groups of decidable and undecidable problems. A decidable problem is one which is solvable; that is, an algorithm can be devised to solve it. It is undecidable otherwise. Decidable problems are further divided into several groups based on the complexity of their solutions. There are problems for which PTIME algorithms exist. Such problems belong to the complexity dir=ltr There exist, however, problems neither proved nor disproved to be in P. All NP-complete problems, and some other NP-hard ones, are among such problems. The Boolean Satisfiability (SAT) problem was the first problem shown to be NP-complete. It is to decide, given a Boolean formula, whether there exists a variable assignment which 'satisfies' the formula, i.e. make is true. All NP-complete problems are efficiently reducible to each other. Therefore, if one of them can be solved in polynomial order of the problem size, all of them can be solved with this order. The NP-hard dir=ltr The goal of this project is to investigate and improve some of the SAT and Max-SAT algorithms. Firstly, the SAT problem and some of its algorithms are studied. Then, the reduction of SAT to other NP-complete problems with relatively quick algorithms is investigated. Although such a reduction is performed in PTIME, the size of the problem instance increases significantly by each reduction. Another method, called interval method, was then proposed and implemented. In the interval method, each variable assignment is represented as a binary number, each bit representing the value of a variable. A special search algorithm is then used to find a satisfying assignment, if any, in the state space of different values for the binary number. Special pruning techniques are used to reduce the size of the state space. A hardware circuit was also designed and tested for some small instances. However, none of these methods was successful in achieving a fast reliable solution to the problem. However, a successful method proposed in this thesis is to preprocess the given SAT instance using a simplification algorithm. The algorithm operates on the input instance and given, as its output, a simplified, yet equivalent, instance. Experiments, based on some standard SAT solvers, shows that the proposed algorithm can remarkably reduce the amount of time required to solve the problem. In particular, the algorithms reduced by about 25% the run time of two popular sat solvers, namely Rsat and Minisat, over several standard benchmarks. In this thesis, in addition to the SAT decision problem, the MAX-SAT optimization problem was investigated. Initially, a new heuristic algorithm called K-Half-SAT was propose... Key Words Satisfiability Problem, Backtracking, Branch and Bound, Simplification Algorithm, Local Search, Hill Climbing