Algorithms can be classified on different basis. A few of them have been considered below:

Type of operations used by the algorithm

Deterministic Algorithms:
A deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. A deterministic algorithm computes a mathematical function, a function has a unique value for any given input, and the algorithm is a process that produces this particular value as output.
Deterministic algorithms can be defined in terms of a state machine: a state describes what a machine is doing at a particular instant in time. State machines pass in a discrete manner from one state to another. Just after we enter the input, the machine is in its initial state or start state. If the machine is deterministic, this means that from this point onwards, its current state determines what its next state will be; its course through the set of states is predetermined. Note that a machine can be deterministic and still never stop or finish, and therefore fail to deliver a result.
Disadvantages:
 Unfortunately, for some problems deterministic algorithms are also hard to find. For example, there are simple and efficient probabilistic algorithms that determine whether a given number is prime and have a very small chance of being wrong. The known deterministic algorithms remain considerably slower in practice.
 Another major problem with deterministic algorithms is that sometimes, we don’t want the results to be predictable. For example, if you are playing an online game of blackjack that shuffles its deck using a pseudorandom number generator, a clever gambler might guess precisely the numbers the generator will choose and so determine the entire contents of the deck ahead of time, allowing him to cheat; for example, the Software Security Group at Reliable Software Technologies was able to do this for an implementation of Texas Hold ’em Poker that is distributed by ASF Software, Inc, allowing them to consistently predict the outcome of hands ahead of time.
 Similar problems arise in cryptography, where private keys are often generated using such a generator. This sort of problem is generally avoided using a cryptographically secure pseudorandom number generator.
ย

NonDeterministic Algorithms:
A nondeterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A nondeterministic algorithm is different from its more familiar deterministic counterpart in its ability to arrive at outcomes using various routes. If a deterministic algorithm represents a single path from an input to an outcome, a nondeterministic algorithm represents a single path stemming into many paths, some of which may arrive at the same output and some of which may arrive at unique outputs. This property is captured mathematically in “nondeterministic” models of computation.
Examples: Merge Sort, Spanning Tree

On the basis of time taken by algorithm to solve the problem

Polynomial Time Algorithms:
An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., T(n) = O(n^k) for some constant k. Problems for which a polynomial time algorithm exists belong to the complexity class P, which is central in the field of computational complexity theory.
Examples: quick sort, basic arithmetic operations etc.
ย

NonPolynomial Time Algorithms:
This group of algorithms consist of algorithms whose running time is not bounded by polynomial expressions.
Example: Travelling salesperson problem

Based on the output of algorithms

Decision Problems:
A decision problem is a question in some formal system with a yesorno answer, depending on the values of some input parameters. For example, the problem “given two numbers x and y, does x evenly divide y?” is a decision problem. The answer can be either ‘yes’ or ‘no’, and depends upon the values of x and y.

Optimization Problems:
An optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete variables is known as a combinatonial optimization problem. In a combinatorial optimization problem, we are looking for an object such as an integer, permutation or graph from a finite (or possibly countable infinite) set.
These categories should be clear before studying NPcompleteness. It helps to go on with the flow of the concepts.
Complexity Classes of Problems
A complexity class is a set of problems of related resourcebased complexity. The simpler complexity classes are defined by the following factors:

The type of computational problem: The most commonly used problems are decision problems. However, complexity classes can be defined based on function problems, counting problems, optimization problems etc.

The model of computation: The most common model of computation is the deterministic Turing machine, but many complexity classes are based on nondeterministic Turing machines, boolean circuits, etc.

The resource (or resources) that are being bounded and the bounds: These two properties are usually stated together, such as polynomial time, logarithmic space, constant depth, etc.
Pcomplexityclass:
P, also known as PTIME, is one of the most fundamental complexity classes. It contains all decision problems that can be solved by a deterministic Turing machine in polynomial time.
A language L is in P if and only if there exists a deterministic Turing machine M, such that:
 M runs for polynomial time on all inputs
 For all x in L, M outputs 1
 For all x not in L, M outputs 0
NPcomplexityclass:
NP is one of the most fundamental complexity classes. The abbreviation NP refers to "nondeterministic polynomial time."
NP is the set of decision problems solvable in polynomial time by a nondeterministic Turing machine.
Example: Travelling Salesperson Problem
Hard to solve NPproblems
Because of the many important problems in this class, there have been extensive efforts to find polynomialtime algorithms for problems in NP. However, there remain a large number of problems in NP that defy such attempts, seeming to require superpolynomial time. Whether these problems really aren’t decidable in polynomial time is one of the greatest open questions in computer science.
An important notion in this context is the set of NPcomplete decision problems, which is a subset of NP and might be informally described as the "hardest" problems in NP. If there is a polynomialtime algorithm for even one of them, then there is a polynomialtime algorithm for all the problems in NP. Because of this, and because dedicated research has failed to find a polynomial algorithm for any NPcomplete problem, once a problem has been proven to be NPcomplete this is widely regarded as a sign that a polynomial algorithm for this problem is unlikely to exist.
NPHard Problems
To understand this, you should know about reduction. In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A reduction from one problem to another may be used to show that the second problem is as difficult as the first. Intuitively, problem A is reducible to problem B if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently. We say A is reducible to B. Different types of reduction are discussed in a subsequent section.
Coming to NPHard, a problem C can be defined as NPHard iff every problem that is in NP is reducible to C.
NPhard problems are often tackled with rulesbased languages in areas such as:
 Configuration
 Data mining
 Selection
 Diagnosis
 Process monitoring and control
 Scheduling etc.
NPcomplete Problems
The complexity class NPcomplete (abbreviated NPC or NPC) is a class of decision problems. A decision problem L is NPcomplete if it is in the set of NP problems and also in the set of NPhard problems.
NPcomplete is a subset of NP. A problem p in NP is also NPcomplete if every other problem in NP can be transformed into p in polynomial time. If any single problem in NPcomplete can be solved quickly, then every problem in NP can also be quickly solved, because the definition of an NPcomplete problem states that every problem in NP must be quickly reducible to every problem in NPcomplete (that is, it can be reduced in polynomial time). Because of this, it is often said that the NPcomplete problems are harder or more difficult than NP problems in general.
Example: Boolean Satisfiability Problem
Satisfiability Problems
 Boolean Satisfiability Problem:
In computer science, Boolean, or propositional, satisfiability (abbreviated SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it establishes if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE. If no such assignments exist, the function expressed by the formula is identically FALSE for all possible variable assignments. In this latter case, it is called unsatisfiable, otherwise satisfiable. For example, the formula “a AND NOT b” is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, “a AND NOT a” is unsatisfiable.
 Circuit Satisfiability Problem:
In theoretical computer science, the circuit satisfiability problem (also known as CIRCUITSAT, CircuitSAT, CSAT, etc.) is the decision problem of determining whether a given Boolean circuit has an assignment of its inputs that makes the output true.
CircuitSAT has been proven to be NPcomplete. In fact, it is a prototypical NPcomplete problem; the CookโLevin theorem is sometimes proved on CircuitSAT instead of on SAT for Boolean expressions and then reduced to the other satisfiability problems to prove their NPcompleteness.
 3Satisfiablity:
Like the satisfiability problem for arbitrary formulas, determining the satisfiability of a formula in conjunctive normal form where each clause is limited to at most three literals is NPcomplete also; this problem is called 3SAT, 3CNFSAT, or 3satisfiability. It is used as a starting point for proving that other problems are also NPhard. This is done by polynomialtime reduction from 3SAT to the other problem.
CookLevin Theorem
The CookโLevin theorem, also known as Cook’s theorem, states that the Boolean satisfiability problem is NPcomplete. That is, any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the problem of determining whether a Boolean formula is satisfiable.
The theorem is named after Stephen Cook and Leonid Levin.
An important consequence of the theorem is that if there exists a deterministic polynomial time algorithm for solving Boolean satisfiability, then there exists a deterministic polynomial time algorithm for solving all problems in NP. Crucially, the same follows for any NP complete problem.
Clique Problem
The clique problem refers to any of the problems related to finding particular complete subgraphs ("cliques") in a graph, i.e., sets of elements where each pair of elements is connected.
A clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NPcomplete, but despite this hardness result many algorithms for finding cliques have been studied.
A clique in an undirected graph G = (V, E) is a subset of the vertex set C โ V, such that for every two vertices in C, there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by C is complete (in some cases, the term clique may also refer to the subgraph).
A maximal clique is a clique to which no more vertices can be added. A maximum clique is a clique that includes the largest possible number of vertices, and the clique number ฯ(G) is the number of vertices in a maximum clique of G.
Vertex Cover
A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. It is an NPcomplete problem.
Formally, a vertex cover of a graph G is a set C of vertices such that each edge of G is incident to at least one vertex in C. The set C is said to cover the edges of G. The following figure shows examples of vertex covers in two graphs (and the set C is marked with red).
A minimum vertex cover is a vertex cover of smallest possible size. The vertex cover number tau is the size of a minimum vertex cover. The following figure shows examples of minimum vertex covers in the previous graphs.
Set Cover
The set covering problem (SCP) is a classical question in computer science and complexity theory.
It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms.
Given a set of elements {1,2,…,m} (called the universe) and a set S of n sets whose union equals the universe, the set cover problem is to identify the smallest subset of S whose union equals the universe. For example, consider the universe U = {1, 2, 3, 4, 5} and the set of sets S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Clearly the union of S is U. However, we can cover all of the elements with the following, smaller number of sets: {{1, 2, 3}, {4, 5}}.
In the set covering decision problem, the input is a pair ({U}, {S}) and an integer k; the question is whether there is a set covering of size k or less. In the set covering optimization problem, the input is a pair ({U}, {S}), and the task is to find a set covering that uses the fewest sets.
The decision version of set covering is NPcomplete, and the optimization version of set cover is NPhard .
Like this:
Like Loading...