A few questions about Computational Problems Complexity Classification

Question

(This might look like just a post to you and you might think I shouldn't have submitted it as a question here but in reality it is some questions put together, so I hope you don't close it)

I only started studying about this topic two days ago and with my math not being really strong (yet) I am struggling to survive. But I am quite interested so I will, somehow!

I decided to begin by drawing the picture of the different categories of problems and this is what I have so far:

Computational Problems are divided in four categories: Decision, Search, Counting and Optimization

Then, we have another set of categories: NP, NPC, NPH and P

P is the class of problems that are solved in polynomial time by a deterministic Turing machine.

NP is the class of problems that are solved in polynomial time by a non-deterministic Turing machine but their solution can be verified by a deterministic Turing machine in polynomial time.

Including some other categories as well, a representation image is featured on the Important Complexity Classes Wikipedia entry.

Question 1: I understand that Turing Machines are only used to help us examine the the capabilities of computers but do non-deterministic machines "exist"?

Question 2: The image above is from a point of view with non-deterministic Turing machines. If they DO NOT exist, the representation is false, as P is included in NP because NTMs can solve both P and NP problems in polynomial time. Am I right or am I missing something?

Question 3: Is there a reason we call them P and NP (which at first confuses because it looks like P olynomial and N ot P olynomial instead of DP (Deterministic Polynomial) and NDP (Non-Deterministic Polynomial)?

Then, NPC is the class of NP problems that all other NP problems can be reduced to, in polynomial time.

And NPH is the class of problems (not essentially in NP) that all NP problems can be reduced to, in polynomial time.

Question 4: Since not all NPH problems are in NP, why is it part of their name?

Question 5: There should exist more than just one categories like NPC, no? To me, which means "to a person with no great math background", NPC is a set of some NP problems that look identical so we could find more NP problems that look identical and have more categories like NPC.

Answer 1

1) It depends what you mean by "exist", but probably the answer is no: we can't build an actual, physical, non-deterministic machine. (Of course, we can't literally build a Turing machine either, since the definition of a Turing machine generally requires infinite amounts of memory; but even if you're willing to fake that by counting a computer as an "existing" Turing machine, we still can't make non-deterministic ones.) Non-deterministic machines are essentially a thought experiment.

2) I don't quite understand this question, but I'll try to restate the relevant facts. A problem is in NP if it is solvable by a non-deterministic Turing machine in polynomial time. So any problem in P is also a problem in NP: since the problem is in P, it can be solved by a deterministic Turing machine in polynomial time. But every deterministic Turing machine IS a non-deterministic machine; it just ignores the additional capabilities. So the problem is also in NP.

3) The short answer is history. P may have been named before people were even considering non-deterministic machines (I'm not sure about the timing). DP would be a bit odd because it suggests that the only relevant question is determinism; but really, the point is that P is the class solved by "ordinary" machines, and other machines are defined from that. If you were thinking about P versus, say, programs solvable by quantum machines in polynomial time, it would be weird to emphasize that P was a deterministic class, because the relevant question would be quantum or not, rather than deterministic or not.

It is a bit confusing for people new to the area, but one gets used to it quickly. The potential confusion of NP with "not polynomial" doesn't last long, because "not polynomial" isn't a natural category to talk about.

4) I've never seen the NP hard problems referred to as "NPH", and google seems to think that you're the first person to use "NPH" to refer to a complexity class. But the term NP appears in the name of the "NP hard" problems because the problems are defined relative to NP. In general, if C is a class, it makes sense to talk about the problems hard for C (relative to some appropriate kind of reduction), and the NP hard problems are a special case of that.

5) The NP complete problems are more than just some class of similar NP problems; they're the "maximal" class. But yes, there could be others, and indeed, if P!=NP, it's a theorem that there are others. But as far as I know, there aren't any "natural" classes: no one has found a groups of problems that all reduce to each other, and are candidates for being not P but NP complete.