Non deterministic Polynomial(NP) vs Polynomial(P)?

Question

I am actually looking for description what NP alogrithm actually means and what kind of algo/problem can be classified as NP problem

I have read many resources on net . I liked

Polynomial problem :- If the running time is some polynomial function of the size of the input**, for instance if the algorithm runs in linear time or quadratic time or cubic time, then we say the algorithm runs in polynomial time . Example can be binary search

Now I do understand Polynomial problem . But not able to contrast it with NP.

NP(nondeterministic polynomial Problem):-

Now there are a lot of programs that don't (necessarily) run in polynomial time on a regular computer, but do run in polynomial time on a nondeterministic Turing machine. These programs solve problems in NP, which stands for nondeterministic polynomial time.

I am not able to to understand/think of example that does not run in polynomial time on a regular computer. Per mine current understanding, Every problem/algo can be solved in some polynomial function of time which can or can't be proportional to time. I know i am missing something here but really could not grasp this concept. Could someone give example of problem which can not be solved in polynomial time on regular computer but can be verified in polynomial time ?

One of the example given at second link mentioned above is Integer factorization is in NP. This is the problem that given integers n and m, is there an integer f with 1 < f < m, such that f divides n (f is a small factor of n)? why this can't be solved in some polynomial time on regular computer ? we can check for all number from 1 to n if they divide n or not. Right ? Also where verification part come here(i mean if it can be solved in polynomial time but then how the problem solution can be verified in polynomial time)?

Your algorithm for integer factorization runs in pseudo-polynomial time. https://en.wikipedia.org/wiki/Pseudo-polynomial_time — Paul Hankin, Jul 30 '16 at 21:53

score 2 · Answer 1 · answered Mar 23 '18 at 17:40

It's probably worth noting how the idea of "checking a solution in polynomial time" relates to a nondeterministic Turing Machine solving a problem: in a normal (deterministic) Turing Machine, there is a well-defined set of instructions telling the machine exactly what to do in any situation ("if you're in state 3 and see an 'a', move left, if you're in state 7 and see a 'c', overwrite it with a 'b', etc.") whereas in a nondeterministic Turing Machine there is more than one option for what to do in some situations ("if you're in state 3 and see an 'a', either move right or overwrite it with a 'b'"). In terms of algorithms, this lets us "guess" solutions in the sense that if we can encode a problem into a language on an alphabet* then we can use a nondeterministic Turing Machine to generate strings on this alphabet, and then use a standard (deterministic) Turing Machine to ensure that it is correct. If we assume that we always make the right guess, then the runtime of our algorithm is simply the runtime of the deterministic checking part, which for NP problems runs in polynomial time. This is what it means for a problem to be 'decidable in polynomial time on a nondeterministic Turing Machine', and why it is often simply phrased as 'checking a solution/ certificate in polynomial time'.

* Example: The Hamiltonian Path problem could be encoded as follows:

Label the vertices of the graph 1 through n, where n is the number of vertices. Our alphabet is then the numbers 1 through n, and our language consists of all words such that

a) every integer from 1 to n appears exactly once

and

b) for every consecutive pair of integers in a word, the vertices with those labels are connected

Ami Tavory · Answer 2 · 2016-07-30T12:28:44.803

Your question touches several points.

First, in the sense relevant to your question, the size of a problem is defined to be the size of the representation of the problem. So, for example, when you write about the problem of a divisor of n. What is the representation of n? It is a series of characters of length q (I don't want to be more specific than that). In general, n is exponential in q. So when you talk about a simple loop from 1 to n, you're talking about something that is exponential in the size of the input. For example, the number "999999999999999" represents the number 999999999999999. That is quite a large number, but it is represented by 12 characters here.

Second, while there is more than a single way to define the class NP, perhaps the simplest one for decision problems (which is the type you raise in your question, namely is something true or not) is that if the answer is true, then there is an "certificate" that can be verified in polynomial time. For example, consider the Hamilton Path Problem. This is (probably) a hard problem to solve, but, if you are given a hamilton path as an answer, it is very easy to verify that it is so; specifically, it can be done in polynomial time. For the Hamilton Path Problem, the path is a polynomial-time verifiable certificate, and therefore this problem is NP.

M Sach · Answer 3 · 2016-07-31T05:07:38.103

-1

Polynomial Time :- Problem which can be solved in polynomial time of input size is called polynomial problem. In plain simple words :- Here Solution to problem is fast. For example sorting, binary search

Non deterministic polynomial :- Theoretically the problems which can be verified in polynomial time irrespective of actual solution time complexity (which can be polynomial or not polynomial). So some problem which are P can also be NP.

But Informally people while conversation/posts use the NP term in below sense Problem which can not be solved in polynomial time of input size is called polynomial problem. In plain simple words :- Here Solution to problem is not fast. You may have to try different permutation/combination or guessing work. But Verification part is fast and can be done in polynomial time. Like input some numbers X and divide the numbers into two groups that difference in their sum is minimum

I really liked the Alex Flint answer at https://www.quora.com/What-are-P-NP-NP-complete-and-NP-hard .Above is just gist of that.

edited Jul 31 '16 at 05:07

answered Jul 30 '16 at 12:30

M Sach

33,416
76
221
314

I don't think that your definition of "Non deterministic polynomial" is correct at all. In particular, if P=NP (which is not yet refuted), then *any* problem in NP *can* be solved in time P. Even if not, P is part of NP, so *some* problems in NP can be solved in time P. – Ami Tavory Jul 30 '16 at 12:40
@AmiTavory Actually you are right. But in generally there two versions of NP i.e. One theoretical and second what people actually mean when they use NP in common conversation/post. I have corrected my post to mention this point explicitly – M Sach Jul 30 '16 at 12:54
I don't follow the paragraph that starts "But generally". I think you're saying that informally "NP" means "NP and not P" (or at least, "NP and I can't prove it's P"), but it looks like there's words/punctuation/grammar missing and it's bad enough to make the result near incomprehensible. – Paul Hankin Jul 31 '16 at 03:25
"some problem which are P can also be NP". Every problem that's P is necessarily NP -- if a problem is in P, you can just recompute the solution to verify the problem. But your definitions are not quite equivalent to the standard ones though (or at least imprecisely worded enough to make it hard to be sure if they're equivalent), so with these definitions it may be true that there are P problems that aren't NP. – Paul Hankin Jul 31 '16 at 03:36
Thanks Paul. Yes generally meant informally here. Corrected this. For second comment theortically you are correct, but my intention is to make it simple and clarify what people often means (informally) when they use the term NP/P.As is said earlier this is just gist of Alex Flint awesome answer – M Sach Jul 31 '16 at 05:13

Non deterministic Polynomial(NP) vs Polynomial(P)?

3 Answers3