Question

In: Computer Science

What is NP? What is P? What is NP-complete? What is NP- hard?


What is NP? What is P? What is NP-complete? What is NP- hard? Give brief definitions. Give an example of an NP- complete problem. Is P equal to NP?

Solutions

Expert Solution

SOLUTION-(4):-

P : P belongs to the set of all decision problems which we can solved in polynomial time by a deterministic Turing machine. Because, it can be solved in polynomial time, it can also be verified in polynomial time. Therefore P is a subset of NP.

NP : NP belongs to the set of all decision problems where instances of the problem for which the answer is yes have proofs that can be verified in polynomial time. That means that if someone gives us an instance of the problem and a certificate (sometimes called a evidence) to the answer being yes, we can examine that it is correct in polynomial time. NP denotes to the Non-deterministic Polynomial time.

NP-Complete : An NP problem A for which it is possible to reduce any other NP problem B to A in polynomial time. Instinctively that means that we can solve B quickly if we know how to solve A quickly. Precisely, B is reducible to A if there is a polynomial time algorithm z to transform instances b of B to instances a = z(b) of A in polynomial time with the property that the answer to b is yes iff the answer to z(b) is yes.

NP-Hard : Instinctively these are the problems that are even harder than the NP-complete problems. NP-hard problems do not require to be in NP (they do not require to be decision problems). The precise definition here is that a problem A is NP-hard if there is an NP-complete problem B such that B is reducible to A in polynomial time. But because any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time. Then if there exist is a solution for one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time.

The 3SAT problem is an example of NP-Complete problem : It denotes to solving the satisfiability problem for an expression in 3CNF form.

Is P equal to NP : Every decision problem that we can solve by a deterministic polynomial time algorithm is also solvable by a polynomial time non-deterministic algorithm. We can solve all problems in P with polynomial time algorithms, whereas all problems in NP - P are intractable. It is not known whether P = NP. Although, many problems are known in NP with the characteristic that if they belongs to P, then it can be proved that P = NP. If P ≠ NP, there exists some problems in NP that are neither in P nor in NP-Complete. The problem belongs to class P if it is easy to search a solution for the problem. The problem belongs to NP, if it is easy to examine a solution that might have been very exhausting to search.


Related Solutions

What is P-Problem? What is NP-Problem? What is NP-Complete problem?
What is P-Problem? What is NP-Problem? What is NP-Complete problem?
Show Integer Programming is NP-complete.
Show Integer Programming is NP-complete.
Show that the following problem is NP-hard. Input: A boolean function in CNF such that every...
Show that the following problem is NP-hard. Input: A boolean function in CNF such that every clause has at most three literals and every variable appears in at most three clauses. Output: An assignment that evaluates the given function TRUE.
Prove that the 0/1 KNAPSACK problem is NP-Hard. (One way to prove this is to prove...
Prove that the 0/1 KNAPSACK problem is NP-Hard. (One way to prove this is to prove the decision version of 0/1 KNAPSACK problem is NP-Complete. In this problem, we use PARTITION problem as the source problem.) (a) Give the decision version of the O/1 KNAPSACK problem, and name it as DK. (b) Show that DK is NP-complete (by reducing PARTITION problem to DK). (c) Explain why showing DK, the decision version of the O/1 KNAPSACK problem, is NP-Complete is good...
For each of the following problems, indicate which are in P andwhich are in NP....
For each of the following problems, indicate which are in P and which are in NP. Forthose you think are in P, give an outline of the algorithm to solve them. For those you think arein NP, explain why you think they are not solvable in polynomial time. (Hint: think about analgorithm to solve these problems, and then determine if it is polynomial.)a. The Smarandache function, S(k), gives the smallest integer m, so that m! can be evenlydivided by k....
Assuming that SAT is NP-hard, prove that both SAT and 3-SAT (which is SAT restricted to...
Assuming that SAT is NP-hard, prove that both SAT and 3-SAT (which is SAT restricted to only having clauses containing at most three literals) are NP-complete.
If np ≥5 and nq ≥​5, estimate P (at least 7) with n =13 and p=0.6...
If np ≥5 and nq ≥​5, estimate P (at least 7) with n =13 and p=0.6 by using the normal distribution as an approximation to the binomial​ distribution; if np <5 or nq <​5, then state that the normal approximation is not suitable. Select the correct choice below​ and, if​ necessary, fill in the answer box to complete your choice. A. P (at least 7) = ​(Round to three decimal places as​ needed.) B. The normal distribution cannot be used.
Show that if G is a group of order np where p is prime and 1...
Show that if G is a group of order np where p is prime and 1 < n < p, then G is not simple. (Please do not use Sylow theorem)
Show that if P=NP then there is a polynomial-time algorithm for the following search problem: given...
Show that if P=NP then there is a polynomial-time algorithm for the following search problem: given a graph, find its largest clique.
Let X be a Bin(n, p) random variable. Show that Var(X) = np(1 − p). Hint:...
Let X be a Bin(n, p) random variable. Show that Var(X) = np(1 − p). Hint: First compute E[X(X − 1)] and then use (c) and (d). (c) Var(X) = E(X^2 ) − (E X)^ 2 (d) E(X + Y ) = E X + E Y
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT