Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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
show 1 more comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.