Statement:
The P Vs NP problem has a classic one line statement whether P=NP? Mathematically P Vs NP states
P = NP or P # NP i.e. whether or not P is equal to NP.
MEANING AND DEFINITION OF
P & NP: -
P states for polynomial time problems, problems that can be effectively solved in polynomial time by using a deterministic computer. Polynomial time means reasonable time in common terms and in technical terms it means that it is expressible in the form of a polynomial equation.
c P problems are characterized by a polynomial equation.
270
271
i.e. P =CnK where n is the size of inputs or data and K is a positive integer. We call that these are of order K, i.e., O (K).
272
Precisely
273
P = Polynomial time i.e. time required to solve a P type problem.
274
C = Arbitrary constant.
275
n =Size of input or data.
276
277
278
279
280
281
282
283
284
K =Order of P type problem.
Hence P represents a class of polynomial in which total numbers of outcomes are proportional to an integral power of inputs.
NP problems are those in which time required to get a solution is unreasonably large, though the cases are too much, to calculate each case itself may need trivial arithmetic only.
Only problem is number of cases, which are too large for a normal computer to handle fully in polynomial time.
NP literally means non- deterministic polynomial time problem i.e. the problem which can be solved in polynomial time only by a non deterministic computational machine only.
285
286
287
A computer in polynomial or reasonable time cannot handle NP problem.
More often than not there are NP problems that may take centuries for a full solution by brute- force method i.e. by method of checking all options.