I can only explain P, NP, and, NP-complete since those are on my exam. Firstly, P and friends are “sets” meaning they hold a collection of something. In this case it is the set of all problems that satisfy certain properties. A problem is something that requires an algorithm to reach a solution for any input. An algorithm is a protocol to complete some sort of procedure… it’s a series of steps. What’s important in P and NP is the number of steps this algorithm completes relative to the input size. We call this runtime. For example, n^2 is polynomial runtime, because as the input grows, the runtime grows exponentially. If the runtime is exponential, like 2^n, then it seemingly doubles or triples every time you increase the input - which for all things computer, is not nice. Any problem that has a known algorithm already to find a solution efficiently (in polynomial time) is in P. If the problem doesn’t, then it may be in NP. If a problem has an efficient “verifier” or something that can take a problem, its input, its solution, and “verify” that the solution is correct for all inputs, then it is in NP. However, this verifier has to be efficient. If something is in NP then we know of a sanity check to test if our solution from some kind of magic and otherworldly algorithm is correct. Naturally, if something is in P, it is also going to be in NP - but I think that’s because the algorithm is only returning true or false, which are called decision algorithms. An example would be: can I color this graph with 3 colors so that two nodes on an edge have different colors?
Lastly, the concept of “polynomial reducibility” becomes relevant. Basically, mathematicians think there is some sort of invisible problem out there that is represented by NP Complete. Like, the Question to all Life, the Universe, and Everything. The reason they think this is because quite a lot of problems seem to be the same problems. As in - rephrasing another problem brings you to another problem you’re familiar with. This is important since if you’re trying to find an efficient algorithm to X and know Y is “the same problem” then find an algorithm to Y, well, you’ve found an algorithm for X too. Since our algorithm has to be “efficient” or polynomial, something is reducible if there is a sort of pre-processing and post-processing step to convert an input to X to an input for Y in polynomial time. The common analogy is that Y is a black box, it computes an answer but can only speak a certain language. So, you translate your native language (problem X) to its language (problem Y), let it compute its answer, then translate its response back.
What this boils down to is, NP-complete is a class of problems to which there isn’t a readily available efficient algorithm for any of them, since they’re all the same NP problem essentially, and finding an algorithm to one means you find one to all of them. NP-C contains quite a lot of problems and most are seemingly unrelated. However, since no algorithm has been found to solve any efficiently, it might seem that none exists. Therefore, if you discover that an NP problem you’ve been so enthusiastically working on a solution for is polynomially reducible to something in NP complete, you should just give up, because other smarter and more talented people have already given a crack at it and failed.
I can only explain P, NP, and, NP-complete since those are on my exam. Firstly, P and friends are “sets” meaning they hold a collection of something. In this case it is the set of all problems that satisfy certain properties. A problem is something that requires an algorithm to reach a solution for any input. An algorithm is a protocol to complete some sort of procedure… it’s a series of steps. What’s important in P and NP is the number of steps this algorithm completes relative to the input size. We call this runtime. For example, n^2 is polynomial runtime, because as the input grows, the runtime grows exponentially. If the runtime is exponential, like 2^n, then it seemingly doubles or triples every time you increase the input - which for all things computer, is not nice. Any problem that has a known algorithm already to find a solution efficiently (in polynomial time) is in P. If the problem doesn’t, then it may be in NP. If a problem has an efficient “verifier” or something that can take a problem, its input, its solution, and “verify” that the solution is correct for all inputs, then it is in NP. However, this verifier has to be efficient. If something is in NP then we know of a sanity check to test if our solution from some kind of magic and otherworldly algorithm is correct. Naturally, if something is in P, it is also going to be in NP - but I think that’s because the algorithm is only returning true or false, which are called decision algorithms. An example would be: can I color this graph with 3 colors so that two nodes on an edge have different colors?
Lastly, the concept of “polynomial reducibility” becomes relevant. Basically, mathematicians think there is some sort of invisible problem out there that is represented by NP Complete. Like, the Question to all Life, the Universe, and Everything. The reason they think this is because quite a lot of problems seem to be the same problems. As in - rephrasing another problem brings you to another problem you’re familiar with. This is important since if you’re trying to find an efficient algorithm to X and know Y is “the same problem” then find an algorithm to Y, well, you’ve found an algorithm for X too. Since our algorithm has to be “efficient” or polynomial, something is reducible if there is a sort of pre-processing and post-processing step to convert an input to X to an input for Y in polynomial time. The common analogy is that Y is a black box, it computes an answer but can only speak a certain language. So, you translate your native language (problem X) to its language (problem Y), let it compute its answer, then translate its response back.
What this boils down to is, NP-complete is a class of problems to which there isn’t a readily available efficient algorithm for any of them, since they’re all the same NP problem essentially, and finding an algorithm to one means you find one to all of them. NP-C contains quite a lot of problems and most are seemingly unrelated. However, since no algorithm has been found to solve any efficiently, it might seem that none exists. Therefore, if you discover that an NP problem you’ve been so enthusiastically working on a solution for is polynomially reducible to something in NP complete, you should just give up, because other smarter and more talented people have already given a crack at it and failed.