P vs NP

[htirwin]

In recent threads in other forums, and in general, I have noticed that most people make the incorrect assumption that NP stands for Non-Polynomial. Many even claim they learned this in a computer science course. Obviously the abbreviation is isn't helpful especially given that P stands for polynomial. Besides that, it seams many/most people assume that P and NP stand for classes of running times of algorithms.

I was wondering if anyone has taken any CS classes where this is what was taught, or if anyone had somehow been suggested this is the meaning through web interactions or else where.

[MiiNiPaa]

given that P stands for polynomial

It stands for polynomial time. And it is actually denotes class of computation complexity: O(N^m) where m is some value, diferent for different algorithms. For example bubble sort is of P complexity, whereas bogosort is not.

I learned it in discrete math class. I believe it is general lack of understanding (abstract fields of mathematics are often usually confusing for casual learner) and many oversimplified "math for dummies" articles are causing this.

[htirwin]

It stands for polynomial time. And it is actually denotes class of computation complexity: O(Nm) where m is some value, diferent for different algorithms. For example bubble sort is of P complexity, whereas bogosort is not.

I learned it in discrete math class. I believe it is general lack of understanding (abstract fields of mathematics are often usually confusing for casual learner) and many oversimplified "math for dummies" articles are causing this.

This is type of misunderstanding I am talking about. In fact this is not what P means in terms of P and NP. P is a set of problems for which there exists polynomial time solvers.

Bubble Sort is in P complexity therefore does not make sense ( in terms of the P of P vs NP ). It is however correct to say that sorting is in P.

I have a hunch that due to the notoriety of P vs NP, and due to the easily mis-understood nature of the terminology, incorrect interpretations of P vs NP have basically gone viral and extend even into many course materials.

So what did they tell you that NP means, or P=NP is supposed to mean in your discrete math course?

[MiiNiPaa]

supposed to mean in your discrete math course?

It is hard to remember what I have been told 8 years ago, but ill try.

tell you that NP means

non-deterministic polynomial time. Can be solved by polynomial time by non-determenistic machine, can be verified in polynomial by determenistic machine.
In short:
NP — there exist short path through the forest and when pointed to one we can check if it is a path and it is short in sensible time. If we would have infinite scouts, we could find path in sensible time too.
P — we know how to find shortest path already.

or P=NP is supposed to mean Are all NP problems (quickly verifiable) are also P (quickly solvable). It is better be not, as it would break cryptography.

Bubble Sort is in P complexity therefore does not make sense

I oversimplified it: yes, it is class of (decision problems only, afair) problems, not their solution. It should be "if bubble sort is the solution for some problem, that problem is in P". Bogosort is interesting one: "is there any parameters for RNG which make bogosort work in one pass on given sequence". It is verifiable in polynomial time, but is not solvable in polynomial time. At least I do not know applicable solution.

[htirwin]

I oversimplified it: yes, it is class of (decision problems only, afair) problems, not their solution. It should be "if bubble sort is the solution for some problem, that problem is in P".

Yeah, it's something that's easy to do, because the distinction between P and the set of algorithms or time complexities that are bounded in polynomial time and the problems that have algorithms with running times bounded in polynomial time isn't really much a big deal informally. That and it's perfectly valid to use P to abbreviate any of those things if you like. But when you talk about NP, the distinction is crucial.

A lot of people think P=NP would mean that all algorithms can be done in Polynomial time. Which is what it would mean if P was a set of time complexities in polynomial time, and NP were a set of time complexities not in polynomial time. But the problem with this is pretty obvious.

Anyways, I was just wondering, because it got me curious. I think I probably had a sort of vague incorrect understanding of P and NP in my first years, and it wasn't until later I finally learned what it actually means. I guess one thing is that it's hard to understand what NP is when you define it as Non-Deterministic ... . I think It would have been better if they used a different name. The definition in a book I'm reading, "Introduction to The Theory of Computation" by Sipser ( which is highly recommended ), has a very simple and easy to understand definition,

NP is the class of languages that have polynomial time verifiers. In simpler terms, they are the problems where if you have a correct solution, a machine can look at it and give you back a yes if it correct in polynomial time.

The best example is Cryptography. If you have the secret key, then you can use it to decode the message quickly ( which is analogous to verifying ). However, cracking by brute force cannot be done quickly )?

[Mats]

NP — there exist short path through the forest and when pointed to one we can check if it is a path and it is short in sensible time. If we would have infinite scouts, we could find path in sensible time too.

This is not correct. NP would not imply infinite scouts. It would say that whenever there was a turn in the path of the forest, you guess and everytime you make a guess, you always take the path that will lead to the shortest path. Also, depending on the exact parameters of your forest path-finding problem, checking the solution might not be in P.

@Original post: I was told the following definitions:

P - The set of decision problems for which a solution can be determined in minimum polynomial time by deterministic Turing machine.

NP - The set of all decision problems for which a proof can be checked in polynomial time by a deterministic Turing machine

Are all NP problems (quickly verifiable) are also P (quickly solvable). It is better be not, as it would break cryptography.

.

Also, do bear in mind that P does not mean quickly solvable. The numbers in the polynomial can be absolutely enormous, as long as it's a polynomial.

[MiiNiPaa]

It would say that whenever there was a turn in the path of the forest, you guess and everytime you make a guess, you always take the path that will lead to the shortest path. Also, depending on the exact parameters of your forest path-finding problem, checking the solution might not be in P.

There are two common simplified explanation how non-determenistic machine works: infinite luck (happens to select best choice) and infinite resources (selects all choices at once, after finding solution retroactively changes selection to unambiguously choose that path). Both are "correct". (And there is one relying on many-worlds interpretation of quantum mechanics which combines infinite resources with infinite luck).

Also, do bear in mind that P does not mean quickly solvable

Writing "solvable in polynomal time" each time is tiring. I saw term "quickly" used in maths books and had no problem wit it as long as they defined what "quickly" means heer beforehand.