(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.