Problems Classification
Problem classification is the process of assigning a level, based on predefined criteria. Problem classification helps to determine the priority and the response time for each problem
problems in which an object is to be classified in one
of the n classes based.
Types
of Complexity Classes
1) P
Class
2) NP
Class
3) NP-hard
4) NP-complete
Non-deterministic algorithms
Nondeterministic algorithms are ones that, at every
possible step, can allow for multiple continuations path.
A non-deterministic algorithm is one in which the
outcome cannot be predicted with certainty, even if the inputs are known.
For example
Imagine a person walking down a path in a forest and,
every time they step further, they must pick which fork in the road they wish
to take.
Class P
Polynomial time problems, commonly known as P
problems, are the problems whose solution can be found in polynomial time.
class P is the set of all decision problems that can
be solved with worst-case polynomial time-complexity. In other words, a problem
is in the class P if it is a decision problem and there exists an algorithm
that solves any instance of size n in O(nk) time, for some integer k.
A simple example of a P problem is linear search.
NP (Non-deterministic Polynomial)
The NP class stands for Non-deterministic Polynomial
Time. It is the collection of decision problems that can be solved by a
non-deterministic machine in polynomial time.
A yes-or-no problem is in P (Polynomial time) if the
answer can be computed in polynomial time.
Example- Knapsack problem
NP-complete class
If a problem is NP and all other NP
problems are polynomial-time reducible to it, the problem is NP-complete.
In NP is NP-complete if every other problem in NP can
be reduced to it in deterministic polynomial time becomes NP Complete
example
Hamiltonian Cycle.
Satisfiability.
Vertex cover.
NP-hard
Non-deterministic
polynomial-time hardness
If any of a class of
computational problems for which no efficient solution algorithm has been found
becomes NP Hard. A problem is NP-hard if all problems in NP are polynomial time
reducible to it, even though it may not be in NP itself.
Example
Qualified Boolean formulas.
No Hamiltonian cycles.
Cook’s theorem, states that the Boolean satisfiability
(SAT)problem is NP-complete. That is, it is in NP, and any problem in NP can be
reduced in polynomial time by a deterministic Turing machine to the Boolean
satisfiability problem.
OR
Cook's Theorem implies that any NP problem is at most polynomial harder than SAT. This means that if we find a way of solving SAT in polynomial time, we will then be in a position to solve any NP problem in polynomial time.
Milan Tomic
Hi. I’m Designer of Blog Magic. I’m CEO/Founder of ThemeXpose. I’m Creative Art Director, Web Designer, UI/UX Designer, Interaction Designer, Industrial Designer, Web Developer, Business Enthusiast, StartUp Enthusiast, Speaker, Writer and Photographer. Inspired to make things looks better.
0 comments:
Post a Comment