I saw this when learning about k-means clustering, but why NP-hard? What about P?
Also,
The P versus NP problem is a major unsolved problem in computer science.
Why?
For further actions, you may consider blocking this person and/or reporting abuse
Read next
Demystifying CXL Heterogeneous Systems with Heimdall Benchmark
Mike Young -
IBM InfoSphere vs. STIBO STEP: Which MDM Wins?
Hana Sato -
The Stack Overflow Error
Jairo Junior -
LLM Quantization: Balancing Accuracy and Efficiency for Real-World Deployments
Mike Young -
Top comments (7)
I'll try. If somebody see a mistake (or a better way to explain that), please let a comment :)
P are problems which can be solved in Polynomial time. It is said that the problem is tractable, which means that the time a computer needs to solve your problem is normally not that long.
NP means Nondeterministic Polynomial time. NP problems can't be solved in polynomial time by a computer (means in a reasonable amount of time). However, it has never been proved, but it's highly suspected. If you have the solution of an NP problem, you could check if it solves the problem in reasonable amount of time; but the difficult part is to find the solution.
The major unsolved problem you speak about is: can you find a solution as quickly as you can verify if a solution solve a NP problem? If you can prove that yes, in that case we could solve NP problems easily.
NP-complete is a class of problem (> 3000 of them) which are NP, but if you can solve one of these problems, you can use the solution to solve every single other ones. You'll be rich if you can do that.
Adding to this, an NP-hard problem is a problem that is known to be at least as difficult to solve as the most difficult to solve problems in the NP complexity class.
A good example of this is traveling salesman problem is a good example of such a problem, at least when what you care about is optimization of the route. Additionally, it also has an NP-complete version (given a length L, determine if a given graph has a tour that is no longer than L, known as the decision version of the traveling salesman problem).
I see. There is also NP completeness.
However, I am not sure what
non-deterministicmeans. (Non-deterministic Turing Machine? -- found YouTube, but will take some time to watch.)So, how to prove something is NP complete? Or, even NP in the first place?
I don't know ;) but you should continue to ask that many questions. Keep it up!
Yes, the 'nondeterministic' in the name of NP refers to a nondeterministic Turing machine (NTM). Problems that are in NP can be solved in polynomial time on an NTM. This also includes problems in P, which are solvable in polynomial time on a deterministic Turing machine.
NP complete problems are, formally, problems in NP for which every other problem in NP is reducible to that problem in polynomial time. In other words, if an algorithm is found for solving an NP complete problem, you can use that algorithm to solve any other problem in NP by combining it with another algorithm that translates from the problem to be solved to the NP-complete problem (and probably make a very large amount of money by doing so, as many important optimization problems are in NP).
There are a lot of problems that a computer can solve quickly, we've called them
P.But there are some we don't know if a computer can solve quickly. If someone already has an answer a computer can quickly check if it's the right answer though. These problems are called
NP.Some problems we know are at least as hard as any other
NPproblem we've come across, these we callNP-hard. Solving any one of theseNP-hardproblems means that we can solve all the otherNP-hardandNPproblems.Wow, thanks for answering. This also makes sense a lot for layman (or 5-year-old)'s term.