How is Agile Unified Process (AUP) different from Rational Unified Process (RUP) ?

Agile Unified Process uses Agile Modelling, which is used for describing the modelling and documentation process based on agile disciplines. The Rational Unified Process (RUP) is also an agile methodology. Here we highlight the differences between the two. Both of these processes are divided into disciplines or workflows, which are carried out in iterations. Agile Unified Process (AUP) is derived from RUP, and we can say it is a simpler version of it. There are 3 disciplines followed by RUP i.e., Modelling, Requirements and Analysis and Design. The AUP being the simple version combines all of them into one discipline. It is because of this that it is easy for the RUP teams to migrate to AUP if they want to. Thus RUP is very flexible and can be merged with agile modeling practices.

> Active stakeholder participation: In RUP projects, stakeholders including customers, users, managers and operators, are often involved as a part of the project disciplines. It is necessary for the team to assign modelling roles like requirements specifier, business process designer etc., to the participating stakeholders. The activeness of the stakeholders is related to less requirement of feedback in the Agile Unified Process.

> Agile Modelling Standards: A significant part in AUP is played by the UML (Unified Modelling Language) diagrams. For maintaining its agility, the agile teams often blend the standards and the guidelines together. On the other side, in an RUP project, the guidelines to be adopted by the teams for creating modelling artifacts are included.

> Gentle application of the patterns: The AUP teams get the full freedom for choosing which modelling patterns to use. However, in RUP, these patterns are defined by the product depending on the modelling disciplines being followed. This practice has led to an enhancement in the performance of Agile Unified Process by easing the way to apply patterns. But, this concept is not as explicit as it should be.

> Application of the right artifacts: The advice for creation of various types of models is provided by the AUP and it is one of its strengths. The recent version of the RUP also provides plenty of advice on creating non – UML artifacts (UI flow diagrams, data models etc.).

> Collective ownership: This concept of Agile Modelling is used for making enhancements in the projects developed using AUP. But, it has to be assumed that the open communication is supported by the team culture. Along with supporting this concept, AUP lays strong stress on issues concerning configuration management. Therefore, the change management processes sometimes can be a hurdle in path of development.

> Parallel creation of several models: This is an important concept of UP. The team is required to check the activitiy diagrams corresponding to each discipline and see if they are being worked up on in parallel. But there is an issue with UP which is that the flow diagrams do not explain this well.

> Creation of the simple content: The simplicity is assumed by the developers. The team needs to adopt the guidelines stating the use of simple models and also the customers must be happy with this. However, many organizations often find it difficult to adopt this culture.

> Temporary models should be discarded: The AUP team is free to decide which models to discard and which models to keep. Travelling light also helps in maintaining simplicity.

> Public display of models: Models should be displayed publicly for facilitating open communication. This way all the artifacts will be available to all the stakeholders

What is Agile Unified Process (AUP) ?

Rational Unified Process, when simplified, gives rise to AUP or Agile Unified Process. Its developer – Scott Ambler, describes it as a simple and very easy to understand methodology for development of application software for business. The agile unified process makes use of agile concepts and techniques but remains true to its origin i.e., the Rational Unified Process. Various agile techniques are employed by Agile Unified Process for developing software:
> Test driven development (TDD)
> Agile modelling (AM)
> Agile change management
> Database refactoring

All these techniques help AUP in delivering its 100 percent productivity. In 2011 the AUP was considered to be 1 percent of the whole agile methodology. In 2012 DAD or Disciplined Agile Delivery Framework superseded the AUP. Since then most people have stopped working on Agile Unified Process. AUP is different from RUP in the sense that it works only on 7 principles:
> Modelling: Involves understanding about how the business is organized around the software and the problem domain of the project, and then identifying a feasible solution for addressing the problem.
> Implementation: The model is transformed in to executable code and basic testing i.e., unit testing is performed on this code.
> Testing: An objective evaluation is carried out for ensuring that the artefact is of high quality. Testing is done for rooting out the defects and validating whether the system works as desired or not. It also includes verification of the requirements met.
> Deployment: The delivery plan for the system is laid out and executed so that the product reaches the customers.
> Configuration management: Managing the access to various artifacts of the system includes tracking the various versions at regular intervals of time, managing and controlling the changes in them.
> Project management: It includes directing the activities of the project to the right track. These activities include risk management, assigning tasks to people, tracking their progress, coordinating with people for ensuring that the system is delivered on time. This is also for making sure that the project is completed within budget.
> Environment: Involves providing continuous guidance i.e., standards and guidelines and tools for ensuring process is going on right track.

The agile unified process follows certain philosophies as mentioned below:
> The team knows what it is doing: People don’t find it convenience to read highly detailed documentation. Timely training and good guidance is accepted by all. An AUP provides links to a number of details if you want, but it does not force you.
> Simplicity: The documentation is kept as simple as possible without going into too much of detail.
> Agility: For maintaining agility, the AUP should conform to the principles and values mentioned in the agile manifesto and agile alliance.
> Emphasizing on high – value activities: Only the activities that affect the project are actually considered. Rest of the activities are not counted.
> Choice of tools: In Agile Unified Process any toolset can be used. However agile experts often recommend using simple tools appropriate for the project.
> The agile unified process can be tailored specific to the needs of your project.

There are two types of iterations in agile unified process as mentioned below:
> Development release iteration: For deployment of the project to demo – area or quality assurance.
> Production release iteration: For deployment of the project to production unit.

These two iterations are a result of refinement of RUP. The RUP’s modelling, requirement and analysis disciplines re encompassed by the disciplines of agile unified process. Even though modelling constitutes an important part of agile process, it is not the dominating factor. 

What is agile modeling (AM)? An explanation. Part 2

Read the first part of this post (Agile Modeling: An explanation - Part 1)

The modeling should be carried forward in small increments. As such it is easy to find bugs if the increment fails or some fault occur. As an agile developer, it is your duty to continuously strive to improve the code. This is just another way of showing that your code works in real, and is not just mere theory. The stakeholders know what they want better than the developers. Thus, by actively participating in the development process and providing constant feedback they can help in building a better software overall.
The principle of assuming simplicity means keeping focus on the required aspects instead of drawing out a highly detailed sketch. It also means using simple notations for depicting various model components, using simple tools, taking information from a single source, rejecting temporary models and updating models only when required. Facilitation of the communication can be improved by making a public display of the models, be it on wall or website, application of standards of agile modeling, collective ownership of artifacts and modeling in a team. Gentle application of the patterns enhances the results drastically.
The formalized contract models are required when you require integrating your system with other legacy systems such as web application or database. These models lay out a contract between you and the owners of these legacy systems. The principles, values and practices of AM have been developed by many experienced developers. With AMDD or agile model driven development we do sufficient high level modeling in the initial stages of the project for making out the scope of the project. In the later stages the modeling is carried out in iterations as a part of the development plan. You might then take model storming road for compiling your code straightaway. Agile practices can be applied to most of the projects. It is not necessary that you should be working on an agile project to benefit from these practices. Also it is not necessary to put all principles, practices and values to use to harness agile advantage. Instead it is better to tailor these practices according to the specifications of your project.
Another way of harnessing agile benefits is to follow AMDD. MDD (model driven development) in its agile form is called agile model driven development. In AMDD before writing the source code we create extensive agile models. These models are strong enough for carrying forward all the development efforts. AMDD is a strategy that seeks to multiply the scale of agile modeling. The main stages in this process are:
> Envisioning: Consists of initial architecture envisioning and initial requirements envisioning. These activities are carried out during the inception period.
> Iteration modeling
> Model storming
> Reviews
> Implementation

It is during the envisioning phase that we define the project’s scope and architecture. It is done using high level requirements and architecture modeling. The purpose of this phase is explore the requirements of the systems as far as possible and built a strategy for the project. Writing detailed specifications is a great risk to take. For short term projects you may like to pare only few hours on this matter. Agile modelers are advised to spend only required time on this phase to avoid the problem of over – modeling. For exploiting the important requirements you might require a usage model. It helps you explore how the product will be used by the users. For identifying fundamental business entity types an initial domain model is used. The issues with the user interface and its usability can be explored using an initial UI model.

What is agile modeling (AM)? An explanation. Part 1

Agile modeling is one of the most trusted development methodologies when it comes to producing an effective documentation and software system. If described at a high level, it comprises of all the best practices, best principles and values required for modeling a high quality software product (this description may seem a bit hyperbolic, but it tends to be true for the most part). These practices are lightweight in implementation, with a lot of flexibility. Although, Agile Modeling is a set of principles and therefore on its own, it is of no use. It has to be mixed with other fuller technologies such as rational unified process, extreme programming, and adaptive software development, scrum and so on. This process enables us to develop software that satisfies all of our requirements. Agile modeling is governed by the following values. Some of these values are extended from extreme programming:

- Communication: All the stakeholders should maintain an effective communication between them.

- Simplicity: Developers should strive to develop the simplest solution possible meeting all the requirements.

- Humility: As a programmer, you should have a sense of humility that you may not know everything and you should allow others to add value to your ideas.

- Feedback: There should be a mechanism for obtaining feedback early in every stage of development.

- Courage: You should have courage to make decisions and stay firm.

The principles on which the Agile Modeling is based are defined by the agile manifesto. Two of these principles are to assume simplicity and embrace changes. Assuming simplicity makes it easy to design software. You are able to cut out unnecessary secondary requirements and focus on the primary needs, thereby reducing the complexity. When you embrace the fact that there will be changes in the requirements, it adds flexibility to your project. As a result, you can develop more flexible projects that can adapt to the changes in requirements, and other changes, over time. 

The software evolves in increments. You should know that it is this incremental behavior that maintains agility of the system. The requirements are ever changing and so there should be rapid feedback mechanism in place through which early feedback can be obtained. With this early feedback it becomes easy for you to ensure that your system is fulfilling all the needs. The modeling should be done with a purpose i.e., if you don’t understand the purpose of your project, its audience or its environment you should avoid working on it unless you are pretty confident. 

It is always wise to have a contingency plan. Therefore, it’s good to have multiple models on standby. There can be a situation in which your primary model might fail, the standby models will provide a back up. One thing worth noting is that agile models are not just mere documentation; they are light weight realizations of your system’s purpose. Once the purpose is fulfilled, the models are discarded. 

One belief of agile developers is that representation is less important than the content. It is the content that matters. Also there are a number of ways in which the same content can be represented. Focus should be maintained on quality work because sloppy work is not valued anywhere. Also adapting to the principles of agile modeling for meeting the environment needs is important. Modeling in an agile manner requires practice. Agile modeling can be applied through various practices. You have to pick the most appropriate one for your project. However there are few fundamental practices that are always important for success of an agile model:

> Parallel creation of several models.

> Application of the right software artifacts depending up on the situation.

> Moving forward through continuous iteration.

One word of caution though! These models are just an abstract representation of the actual systems and therefore cannot be accurate.

Bug fixing: Ensuring that there is regular contact with outside users

Bug fixing is an integral part of the product development process, and unless the bug finding and bug fixing process starts tapering down near the end of the product development cycle, you are in deep trouble. Near the end of the cycle, is one of the most stressful time for the product development team. After all, when you are nearing the end of the development cycle, any new defect that comes through can cause huge problems for the team and for the schedule. If the defect was serious, then there are many issues that come to light. One needs to figure out whether the area was tested well enough before during the earlier parts of the schedule, as well as figure out what the risk was in terms of making the fix of the defect. If the fix can impact a large enough area, then the team might well want to not make the fix and take the defect. If a serious defect fix has been made near the end of the schedule, then there is a compromise that needs to be made in terms of the amount of time available for testing of the fix.
But this post was not about this problem. The problem is more of a derived problem, In my experience with multiple development cycles, I have seen defects come near the end, or become more serious near the end, where the defect was seen earlier with external users (these are users who are not part of the core team, but could be users who are part of a restricted pre-release or a public release). The challenge comes in terms of recognizing these defects as valid defects.
The advantage of outside users is the amount of diversity that they have. People outside the core team who are testing the product do a lot more adhoc testing, trying out different combinations that the core team would not be testing. In addition, the diversity of equipment that outside users have far strips the diversity of equipment available with the core testing team - they would have more types of machines, different sets of equipment, and so on. This provides an advantage that the core team would be well equipped to use.
At the same time, there is a cost associated with the pre-release users. Some of the defects that they find are already known to the core team, other defects may not be able to be replicated by the core testing team, and yet others are significant defects that the core team takes up for fixing. For a number of defects, it may have been critical for the outside user, but the core team would make a choice that either the defect was not been able to be replicated, or the area was not of a high priority to be taken up for fixing.
However, this is where we had problems and had to make changes. Near the end of the cycle, we would find some defects during the final stage of adhoc testing that had been found by outside users but which the team had dismissed. The amount of impact to the schedule and increasing the stress level of the team was one of the byproducts. To control this problem, we decided to make a lot of effort to evaluate the defects raised by the outside users, including remote control of their machines to try and find the defect cause, spending much more time to analyze the defect, and we had some success in this kind of effort that we were putting. We were able to figure out some of these more serious defects and this in turn reduced the chance of getting some of these defects near the end of the cycle, and also had the byproduct where the outside users felt that their defects were getting more serious attention and produced some great defects.

What are some of the limitations / challenges of Adaptive Software Development (ASD)?

The Adaptive Software Development (ASD) culture is the result of efforts of Sam Bayer and Jim Highsmith in the field of rapid application development. The methodology aims at developing software that is capable of adapting continuously to the changes in the working environment. In ASD, in place of the waterfall approach, we have cycles of speculating, collaborating and learning. It is because of this dynamic cycle that the software is able to adapt to changing state of the requirements and learn through it. The cycle is very much tolerant to changes, driven by the risk, timeboxed and works in iterations.
Throughout the process the ASD life cycle remains focussed on the mission. Since adaptive software uses the information available from the environment for improving its working pattern, with the increasing complexities it becomes difficult for it to gather usable information. The effectiveness of the adaptive software development is reduced by the complexities of the environment. Today we expect more from the software and in such critical situations in which we never expected earlier. Thus complex environments pose a great challenge. There are three dimensions that contribute to this complexity:
> Increasing number of users: Now not only professionals, everyone uses software.
> Increasing number of systems: More number of systems means more number of interactions between them. Most of the system networks that we have now are heterogeneous. Maintaining homogeneous networks is easy.
> Increasing number of resources and goals: The most common trade off that programmers make is between time and space. Now there are several other things to worry about including security, bandwidth, money, quality, resolution and so on.

These three dimensions make it even hard for the designers to design a system. It is impossible to predict about these factors and therefore always right decisions can’t be made. This results in a product with a short lifetime. Every now and then upgrades will be required for modifying the software. Other factors related to complex environment that pose a challenge for adaptive software are:
> uncertainty
> hidden inputs
> non – deterministic
> unique
> continuity
> real world

Other things that put limitations on adaptive software development are following 4 myths:
> The traditional belief is that the specifications must be determined first. But this is not the case always. One specification can be taken at a time and refined in later stages. The aim should be combining several components together successfully and not developing a single app.
> People usually believe by maintenance that program code has degraded. The truth is that it remains the same while its environment changes. So maintenance involves evolution of the code to satisfy these changing needs. When programmers view this through a maintenance perspective, they tend to preserve the old program structure.
> It is undeniable that abstraction has an important role to play in the development process. But when we treat a process as a black box object we are actually ignoring the practical problem it faces of resource usage. In adaptive software development we take a new approach called open implementation. Here the modules have two interfaces – one for input/ output and the other checking performance. These two interfaces are perpendicular to each other. ADS also adds a feedback mechanism to this orthogonal interface system making it much better.
> While designing software we consider all the possible alternatives. The desired one is kept and the others are rejected. This means that once a requirement changes, we again have to see what alternatives are available and which one can be implemented. This might require changing all of the program structure. The best thing here to be done is programming the system such that it reconfigures itself.

How is Adaptive Software Development (ASD) different from Scrum? Part 2

Read the First Part (Adaptive Software Development being different from Scrum - Part 1)

For understanding the further differences between the two, it is important that we know what Agile Development is. The Agile manifest defines the agile methodology. There are 7 agile methodologies; namely XP, Crystal orange, Scrum, Adaptive Software Development, DSDM, Pragmatic programming and Feature – driven development. All these methods differ in their mechanisms and the parameters they take. All these methods have a different agile life cycle. For ASD, it depends on what techniques we are going to use. Generally speaking it doesn’t have a life cycle of its own. In contrast to this, scrum has an abstract lifecycle which packs certain activities in to its schedule.

However here we discuss differences based up on a lifecycle having some general phases.
- Project initiation: This step includes justification of the project and determining the requirements.
- Planning: Laying out an elaborate plan for development and leaving some gap for contingency actions. Scrum doesn’t have choice for including optional phases. It must work within predefined options, whereas the adaptive software development can have many options because it does not limits itself to few techniques.
- Elaboration of requirements: This stage is optional. The requirements are explained in great detail. Scrum does not implement this stage separately, but, it may be done in Adaptive Software development. Since the requirements are still in high level, they need to be broken down in to simpler specifications. The requirements are collated in to requirements document after classification. This document also contains use cases apart from the requirements.
- Architecture: Both scrum and ASD are based on agile principle of, design today and refactor tomorrow. Software developed using ASD can be modified to suit the changing environment just by adjusting their software capabilities and leaving the hardware unchanged. Software developed through scrum has to be modified through manual intervention and may even require to change hardware. A system architecture document is prepared in this phase.
- Release: The software is released to the customer. It has one timebox at least. Scrum can have many releases depending upon the development span of the project. Adaptive software usually delivers product in one go.

One of the important questions to be asked during project initiation phase is that whether to invest more or not? Not all methods answer this question. However addressing this question is an important part of the adaptive software development. Scrum doesn’t address this question explicitly. Next step is choosing the appropriate method. Scrum claims that it can be used for any project. Adaptive software development creates a list of all alternatives that can be used and chooses the best one.
The level of formality to be maintained in scrum is given by documents such as running code and backlog. In adaptive software development there are many too many choices to choose from. It makes use of vision statements for clearing out the confusion. Scrum defines a sprint goal which is a kind of timebox vision i.e., it follows one choice for some time and then can change if required.
Scrum avoids elaboration phase for speeding up the delivery. It uses product backlog maintained by the product owner.
Since adaptive software development may have an elaboration phase, it may also have a draft plan initially which may turn into a complete plan after determination of requirements. Scrum plans based on timeboxes.
Both methodologies help you work faster creating products with better quality. The agile customer too is an important role in the agile process. The customers are responsible for providing input during prototyping sessions. The organizing and controlling of user testing is the responsibility of the user. 

How is Adaptive Software Development (ASD) different from Scrum? Part 1

Adaptive software development and scrum both come under the overall heading of agile software development, but are two different beasts with differences between them. These are two different approaches with the same aim i.e., agile development. Below, we will write more on what differentiates the two.
It is necessary to know the differences between these two approaches since Scrum, as a part of agile software development is already a very famous methodology, whereas the adaptive software development is relatively new, but also a strong upcoming methodology ready to take the software development market by storm. Agile methods are always preferred over traditional development approaches to incorporate major factors such as increased levels of customer participation and satisfaction, project delivery flexibility, and acceptance of ongoing requirements or design changes at any level in the development process. This is the usual development scenario and that is why agile development methods are used mostly.  Most commonly used agile methods include:
-  Adaptive software development
- Scrum
- Feature driven development
- Extreme programming

Even though all these strategies aim at the same set of objectives (well almost), they do take somewhat different paths (having some items common, and yet others are different). It is important to know the differences between them. Otherwise how you are going to maintain agility in your development structure? Comparison between different agile methodologies, their common points and differences lets the managers choose the most appropriate agile method for their software characteristics.
There are many traditional techniques for drawing comparisons between 2 software development techniques. In this post, Scrum and ADS have been compared on basis of 2 areas, namely software construction and software requirements.
First difference between adaptive software development and the scrum approach is that in the former, there is no predefined technique to be followed. In scrum there are certain predefined techniques to be followed. On the other hand the focus of adaptive software development is on the end result rather on the steps. Adaptive software development methodology implements a particular technique only if it is required.
Since the last two years agile principles have encompassed methods such as extreme programming, feature driven development, adaptive software development and so on.  So far companies using scrum or adaptive software development have been able to deliver successful products. Scrum is described as a process for management and control used for cutting down the complexity. This is used by the organizations who want to deliver products faster. This approach to software development has been used on advanced development methods including software; it usually works well in the object – oriented development environment.
On the other hand adaptive software development is described as methodology for developing reliable and re – adaptive software. It is used by the organizations who want their products to function in a wide range of changing conditions. Software built with this approach are capable of reconfiguring themselves to better suit to the environment. It can be used under any kind of environment. Any technique can be applied here to make software as much flexible as possible. The owners are responsible for estimating backlog items in scrum. In adaptive software development it is mainly the task of the developers.
Scrum follows time-boxing method for speedy delivery. At the start of each timebox, a sprint planning meeting is held. A backlog that can be achieved is picked up by the team members and they decide how it can be achieved.
Scrum may have 1 to 4 teams with 5 – 9 members and adaptive software development may have even more number of teams dedicated to each phase of development process. Agile developers play a number of roles – analysing, estimating, designing, coding and testing. Even though the typing burden is less, there is a lot of stress because of the short frames. But you get to see your progress through user reviews and daily meetings.

Read next part  (Adaptive Software Development being different from Scrum - Part 2)

What is Adaptive Software Development (ASD)?

There are many a software development processes, with adherents and proponents for each one of them. Here we discuss about one of them i.e., ASD or Adaptive Software Development. This process is a result of Sam Bayer’s and Jim Highsmith’s efforts concerning RAD process i.e., rapid application development. ASD is based up on the principle that the development process must be continually adapted to the work at hand as a normal affair.
This development process is sometimes used as a replacement for the traditional waterfall approach. The steps in the waterfall model are replaced with repetitive sets of cycles of speculation, collaboration and learning. This cycle is quite dynamic in nature and allows us to maintain a continuous learning process. It also makes it easy to adapt to the project’s next state. An ASD life cycle is characterized by the following characteristics:
• Mission – focused
• Feature -  based
• Iterative
• Timeboxed
• Risk driven
• Tolerant to changes

Here by speculation we mean “paradox of planning”. Adaptive software development assumes that in the mission of a project, fault in certain aspects of it can be traced to all stakeholders’ mistakes. These mistakes are usually made while defining the requirements of the project. Efforts concerning the maintenance of work balance and environment and adapting to the changes in the environment (caused mainly due to requirements, technology, software vendors, stakeholders and so on) come under collaboration.
The learning cycle on the other side consists of many short iterations involving designing, building and testing. The aim of these iterations is to gather knowledge based up on small mistakes made and based up on false assumptions and then correcting them. This leads to great experience in the domain.
A lot of money and time goes into developing a piece of software, but it still proves to be brittle in some unexpected situations. Then how does adaptive software development makes it better? As the name suggests, ASD is focused up on development of such programs that are capable of readily adapting in the event of changes resulting from user requirements and development environment. It includes an explicit representation of the actions that the program can take and also the goals of the user. With this it becomes possible for the user to change the goals without rewriting the code. It is often used for producing what we call as the agent based applications.
We also have object - oriented programming and structured programming methodologies for developing software. With object – oriented approach the reorganization is easy with the changes because here we divide the functionality in to different classes. But still it requires the programmer to intervene to make some change. Therefore, this approach is kept confined to developing user – initiated event based applications. The structured programming was used to develop input/output based applications only since it cannot tolerate any changes in the specifications. The database managing programs are a typical example of this kind of applications.
There are several other methodologies for developing software. But they only provide solution for managing the changes rather dealing with them. It’s only adaptive software development that gives a real way of adapting to the change and dealing with it without having a programmer’s intervention. The best thing about adaptive software development is that it collects information about the environmental changes and uses it for improvement of the software. But today’s complex software and operating environments are making it less effective. Factors such as increasing number of users, systems, number of interactions, resources and goals etc. lead to complexity of the software. Now apart from time and space, programmers have to look out for money, security, resolution and so on.

What is Boolean satisfiability problem?

The Boolean satisfiability problem is often abbreviated to SAT. In the field of computer science the Boolean satisfiability problem is concerned with the determination of whether or not an interpretation exists, satisfying some given Boolean formula. The other way round, we can say that it is established when in a given Boolean formula; the variables can be assigned in such a way that upon evaluation, the value of the formula is TRUE. If any such assignment is not found, the function that the formula expresses is FALSE for all the ways in which the variables can be assigned. In this case, the problem is said to be unsatisfiable and satisfiable in the former case. Consider the following examples for a better understanding:
- X AND NOT y: This problem is satisfiable since we can find many values for which x is true and y is false.
- X AND NOT x: This problem is unsatisfiable since ’a’ cannot have two values at the same time.

This Boolean unsatisifiability problem actually falls under the category of the NP – complete problems. Till date we don’t have any algorithm that can effectively solve all types of such problems and it is also believed that there is no such algorithm. However there exists a number of problems involving decision and optimization that can be transformed into the SAT instances. The algorithms that have been used to solve a large subset of these problems have been grouped in a class called the SAT solvers. The application of the SAT instances is in the following fields:
- Circuit design
- Automatic theorem proving

Extensive research has been going on for extending the capabilities of the algorithms for solving SAT. but, presently we don’t have any such method that can deal with all the instances of the SAT. A Boolean expression also called as the propositional logic formula is composed of the operators: AND, OR, NOT, () etc. and variables. A formula can be called satisfiable only if it evaluates to be TRUE through assigning the variables appropriate logical values i.e., whether TRUE or FALSE. This formula is used for checking the satisfiability of a SAT instance. Another type of problems falling under this category is decision problem. This type of problems plays a major role in the following fields:
- Theoretical computer science
- Complexity theory
- Artificial intelligence and
- Algorithmics

We have many cases of the SAT problems where we need to have formulas with a certain structure. A variable or a literal is of two types namely the positive literal and the negative literal (negative of a variable). Then we have a clause two which is nothing but a single literal or a disjunction of the literals. If a clause consists of 0 or 1 positive literal, it is said to be a horn clause. If a formula is a conjunction of the clauses, it is a CNF (conjunctive normal form) formula.
It has been observed that defining the notion of generalized CNF formula is useful for solving some instances of the SAT problems. Different problem versions occur due to the different sets of the allowed operators. The Boolean algebra laws can be used for transforming every propositional logic formula in to its CNF equivalent form which might be longer than the one in its original form. SAT problems were the first problems discovered under the field of the NP- complete problems. Before 1971, this concept didn’t even exist. If the formulas can only be used in the disjunctive normal form, SAT is said to be trivial. These formulas are satisfiable iff only one of their conjunctions can be satisfied.