Question

What does it mean when we say an algorithm is NP?

Answer 1

It means it's Non-deterministic Polynomial time.

Answer 2

and what does that mean?

Answer 3

It's a computing science term, it's one of the millenium math questions that are currently unanswered.

Answer 4

I wanna know what it means :(

Answer 5

Ullere -- no, what's unanswered is if P = NP.

Answer 6

Ah good shout ktk, thats the only time I've heard it used.

Answer 7

http://www.indiangeek.net/wp-content/uploads/Programmer%20competency%20matrix.htm

Answer 8

NP means a problem hard enough that it can't be solved in polynomial time, but an answer can be verified in polynomial time

Answer 9

like the towers of hanoi?

Answer 10

@adg :Read here : http://en.wikipedia.org/wiki/NP_(complexity)

Answer 11

solved and verified, what's the difference?

Answer 12

I don't think hanoi is NP hard, no. The travelling salesman problem is the classic NP-hard problem, i.e. find a minimum distance route through a graph that touches every vertex

Answer 13

I don't think tower of hanoi is NP

Answer 14

Solved means finding a solution. Verified means, you are given a solution and verify that it is correct.

Answer 15

so dynamic programming can be used to solve NP?

Answer 16

that's sort of orthogonal. the point of NP is there's no polynomial-time algorithm that finds a solution. typically, approximation algortihms are used.

Answer 17

Oh yeah traveling salesman, Do you know the exact problem? Someone told me about it a year back I forgot hehe

Answer 18

Ishaan hit the google buddy :P

Answer 19

Yeah Right lol

Answer 20

sorry

Answer 21

agd, you are a mystery. you say you're not enrolledin school but you ask a wide variety of questions over a huge number of topics. what's the deal?

Answer 22

@ktklown:It's a mystery for me too.