Question

1) What is your INFORMED opinion on the NP problems? Does a deterministic polynomial time algorithm exist or not? Your answer should be a well-thought out and informed argument consisting of several paragraphs at least. No credit for poor grammar and simplistic answers. Your argument should be convincing and strong.

EXPLAIN IN DETAIL

Answer 1

Solution : Basically, the problem which can solve in a verifiable polynomial time is known as NP problem. These are generally decision problems.

NP problems can be verified with in a polynomial time. Let suppose a person solved a problem in A time then the other person can verify it possibly in the less time as compare to this A time.

Here P is called as set of problems which can solvable within a polynomial time.

NP – complete problems are basically the difficult problem in the NP set of problems.

A decision problem L will be NP – Complete only if the below two points are true:

1. L is one of the NP set problems as the solution of NP-complete is possible to verify easily but there is not any effective solution.
2. Each problem is reducible to L in the polynomial time in the NP problems.

And if any problem is fulfilling the second property only here then it will be considered as NP hard problem.

Here is a diagram below to show the NP problem structure.

NP Hard NP complete NP