However, I am not sure what non-deterministic means. (Non-deterministic Turing Machine? -- found YouTube, but will take some time to watch.)
A common misconception is that the NP in "NP-hard" stands for "non-polynomial" when in fact it stands for "non-deterministic polynomial acceptable problems".[4] It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven.[5] Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class.[6]
So, how to prove something is NP complete? Or, even NP in the first place?
Coding for 20 years | Working for startups for 10 years | Team leader and mentor | More information about me: https://thevaluable.dev/page/about/
Twitter: @Cneude_Matthieu
I'm a Systems Reliability and DevOps engineer for Netdata Inc. When not working, I enjoy studying linguistics and history, playing video games, and cooking all kinds of international cuisine.
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).
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
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).