# A few questions about Computational Problems Complexity Classification

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

• I know nothing about this material, but I do know there is a preference for individual questions. There is little wrong with you being curious about topics that are in the future of your studies, however, this site is not really intended for tutorials. Perhaps you might break this into small pieces that admit short answers. – Will Jagy Oct 6 '10 at 20:59
• My understanding is more mathematical theoretical computer science questions are okay here but this collection of questions might be more appropriate for: cstheory.stackexchange.com – Ryan Budney Oct 6 '10 at 21:15
• I started this post by saying I understand this might not be the appropriate place so feel free to close the question. Sorry for the inconvenience. :) – SebKom Oct 6 '10 at 21:30
• 1&2:What do you mean by exist? Sure there exist programs implementing NP-solving algorithms (with the help of a random generator). Even if not, I don't understand your worries in 2. 3&4: The people who chose those abbreviations probably just didn't think they were confusing. When you get used to them, so will you. 5:NPC problems are those which, if you can solve them let you solve any other NP-problem, so they have the maximal complexity inside the NP-class (I wouldn't say they look identical). You could ask for other complexity classes - that makes sense. – Peter Arndt Oct 6 '10 at 23:44
• A non-deterministic machine exists because we can define it (Hello, Plato!). More seriously, if that definition bothers you, merely consider NP to be the class of all decision problems for which an answer can be verified in polynomial time. – Suresh Venkat Oct 7 '10 at 5:10