Difference between NP, NP complete and NP-hard Problem ?

More Chandra Prakash Meena's questions See All

Which background extraction technique is better statistically ??

05 June 2017 4,811 4 View

Model a neural network with higher output variable then input ??

06 July 2016 7,967 4 View

Which kind of Machine learning is Hidden Markov Model ??

31 December 2015 4,674 6 View

Solving 9x9 Sudoku Puzzle using GA?

10 November 2015 5,557 2 View

Bee royalty offspring algorithm for classification ?

06 July 2015 9,998 0 View

Is there a deep reason for using the squared modulus of the wave function as the probability density of the existence of the particle?

I think we were all surprised at the first time we got to know quantum mechanics that the squared modulus of the wave function is the probability density of the existence of the particle? The role...

28 February 2021 6,282 9 View

How to plot the probability paper of Gumbel distribution using R programing?

In R-studio, there are many commands of Gumbel package. Arguments are also different. I`m asking about the alpha parameter of the Copula which must be greater than 1. If this is the one used to...

25 February 2021 5,229 3 View

How can I multiply values with standard distribution and with triangular distribution?

I am calculating emissions considering the uncertainty of the data to do Monte Carlo simulation. Some variables such as yields have normal, lognormal or even uniform distributions. These must be...

03 February 2021 6,318 5 View

How to prove possibility/impossibility to analytically solve the functional equation f(a ln x^2)/f(x)=x/2a; and how to find out the solution?

This is my very first encounter with functional equation of this kind, and methods of series solution and differential equations are of not much help. The solution to this problem, or at least the...

25 January 2021 6,053 5 View

P-value of Dirichlet statistics in a closed-form?

Do we have a mathematical formula to compute the p-value of an observation from the Dirichlet distribution in exact sense at https://en.wikipedia.org/wiki/Exact_test?

26 December 2020 8,296 4 View

Bell's inequality from probability theory?

It is said Bell's inequality is a consequence of probability theory, which has nothing to do with quantum or not quantum. There are many papers discuss this issue, but I don't know which one is...

22 December 2020 8,254 3 View

How can I calculate degrees of freedom and write F for repeated measure ANOVA?

How can I calculate and report degrees of freedom for repeated mesure ANOVA? I have 48 observations N=48 and 2 factors of 3(P) and 8(LA) levels. I calculate degrees of freedom as follows: dF P =...

19 November 2020 5,682 5 View

Is it correct to use Inverse transform sampling to model distribution by Cumulative distribution function given in the numerical form?

I have the energy specter acquired from experimental data. After normalization, it can be used as a probability density function(PDF). I can construct a Cumulative distribution function(CDF) on a...

11 October 2020 3,866 3 View

Difference between distribution function and probability distribution function?

Could you make some points about the difference between distribution function and probability distribution function?

04 October 2020 4,918 9 View

How to combine/add two Beta Distribution curves?

Hello, I am currently working on Beta Distribution, and I am using the distribution to model a knowledge/opinion into the software. The user adjusts the alpha and beta values of Beta...

12 September 2020 6,569 5 View

Stephen Politzer-Ahles

The following might help:

https://en.wikipedia.org/wiki/NP_(complexity)

https://en.wikipedia.org/wiki/NP-completeness

https://en.wikipedia.org/wiki/NP-hardness

Gour Sundar Mitra Thakur

This is all about how much time a program can take to run.

I am satisfied with the discussion I found in the following link:

https://www.quora.com/What-are-P-NP-NP-complete-and-NP-hard

This link is also helpful:

http://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard

Chandra Prakash Meena

Gour sir, thank you for the links

Saptarsi Goswami

NP -Complete

Let me try to explain let's assume you have two computers one is super powerful , let's call it a solver and the other with limited capacity let's call it verifier. The verifier can not solve a hard problem in polynomial time , but given a solution it can verify , whether it is an optimal solution or not. Any problem which verifier can verify the solution in polynomial time is an NP Problem.

Decision and Search Problems

Generally the problems can be classified as either a decision problem or a search problem. Decision problems are simpler and you expect to get yes, no solution from them. It can be shown , that with some intelligent techniques you can convert this problems. This is useful for reducing the problem.

Cooks Theorem:

This talks about reducibility that we can convert one hard problem to another hard problem. The basic problem is that of Satisfiability problem and it can be shown that maximal clique , vertex cover and independent set are reducible to the satisfiability problem. The argument is if we can solve any one of them then we can solve all of the problem. Now this set of problems are np-hard.

Any problem which is 1) np and 2) np-hard are np-complete.

Hope this helps!