Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 3 down vote favorite

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

share|improve this 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 Rizos♦ 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 Rizos♦ Apr 19 '12 at 11:59

closed as not constructive by Yannis Rizos♦ 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 specific 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, see the FAQ for guidance.

2 Answers

up vote 2 down vote

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

http://stackoverflow.com/questions/2404144/relating-np-complete-problems-to-real-world-problems

There's some interesting book and website links there.

share|improve this answer
up vote 3 down vote

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

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