Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

I need to know the real life or real time examples of above mentioned problems thanks!!

share|improve this question

closed as not constructive by Yannis Apr 19 '12 at 11:18

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. If this question can be reworded to fit the rules in the help center, please edit the question.

What do you mean by "real time"? The complexity classes are defined by measuring the steps of a turing machine. This is pretty far from real time. –  scarfridge Apr 18 '12 at 6:42
I can't understand why 5 people (so far) think this question shows research effort. There's no indication that you've even looked at the Wikipedia pages for the complexity classes listed. –  Peter Taylor Apr 18 '12 at 15:03
@PeterTaylor Use your flags... –  Yannis Apr 19 '12 at 11:19
@YannisRizos, I downvoted it, because that's what the UI pushes as the correct response to a question without research effort. Is there some meta discussion I missed? –  Peter Taylor Apr 19 '12 at 11:53
@PeterTaylor The need for at least some minimal research is scripted in our "how to ask" guidelines. Down voting was the correct approach here, but since you identified the question as problematic (and it was being unvoted, although obviously problematic) a flag would also be useful. –  Yannis Apr 19 '12 at 11:59

2 Answers 2

P: testing whether a number is prime. (See: http://www.jstor.org/stable/10.2307/3597229)

NP: integer factoring because it is easy to check whether two numbers multiply to a desired number. (Actually any P problem is also in NP.)

NP-hard: traveling salesman (See: http://en.wikipedia.org/wiki/Traveling_salesman_problem)

NP-complete: decision version of traveling salesman

share|improve this answer

Take a look at the answers and comments here on this SO question ...


There's some interesting book and website links there.

share|improve this answer

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