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?

Solutions

Expert Solution

ANSWER: P- Polynomial time solving . Problems which can be solved in polynomial time, which take time like O(n), O(n2), O(n3). Eg: finding maximum element in an array or to check whether a string is palindrome or not. so there are many problems which can be solved in polynomial time.

NP- Non deterministic Polynomial time solving. Problem which can't be solved in polynomial time like TSP( travelling salesman problem) or An easy example of this is subset sum: given a set of numbers, does there exist a subset whose sum is zero.

NP-Complete -- The group of problems which are both in NP and NP-hard are known as NP-Complete problem.

Now suppose we have a NP-Complete problem R and it is reducible to Q then Q is at least as hard as R and since R is an NP-hard problem. therefore Q will also be at least NP-hard , it may be NP-complete also.

venereology answered 2 years ago

Next > < Previous

Related Solutions

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?

Show Integer Programming is NP-complete.

Prove that the partition problem is NP-complete by giving a polynomial time reduction of the subset-sum...

Prove that the partition problem is NP-complete by giving a polynomial time reduction of the subset-sum problem to the partition problem.

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....

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)

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

If np ≥ 5 and nq ≥ 5, estimate P(fewer than 3) with n =14 and...

If np ≥ 5 and nq ≥ 5, estimate P(fewer than 3) with n =14 and p = 0.4 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(fewer than 3)= or B. the normal approximation is not suitable

QQQ3 When large samples (np > 5 and n(1 - p) > 5) are associated with...

QQQ3 When large samples (np > 5 and n(1 - p) > 5) are associated with hypothesis tests for a single population proportion, then the associated test statistic will be is a z-score. True or false? QQQ7 In the P-value approach to hypothesis testing, if the P-value is less than a specified significance level, then we fail to reject the proposed null hypothesis. QQQ10 A Type I error is the error made in failing to reject an incorrect null hypothesis....

If np >= 5 and nq >= 5, estimate Upper P( fewer than 6) with n...

If np >= 5 and nq >= 5, estimate Upper P( fewer than 6) with n =13 and p= 0.5 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. P(fewer than 6) = ?

Subjects