Full width home advertisement

Travel the world

Climb the mountains

Post Page Advertisement [Top]

The classes P and NP

Complexity theory attempts to define such differences through a formal criterion for what is meant by a mathematical problem feasibly be decidable ,  that is to say that this can be resolved by a conventional Turing machine with a number measures which are proportional to a polynomial function of the size of input. The category of problem with this property is known as P ( polynomial) - and among the first three of the above-described problems. P can be shown formally distinguished from several other classes, such as to be EXP ( exponential time).Third problem which is fitted from above. The second problem of the above is included in a complex class known as NP ( non-deterministic polynomial) - consists of problems that can certainly by a computation of a non-deterministic Turing machine in a number of steps that a polynomial function, determines the size of the input.

P and NP are two different complexity classes defined in two different Turing Machine.

P-class is an algorithm is a member of the P-type as required to obtain a polynomial time to get an output, deterministically. NP –Class is an algorithm is a member of NP. This class takes polynomial time to verify output, non-deterministically. A Turing machine can be used synonymous with an algorithm

No comments:

Post a Comment

Bottom Ad [Post Page]

| Designed by Colorlib