224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
The work of Cook and Karp in early 70’s gave birth to the most important and fundamental concept of computational complexity, NP-Completeness and its most fundamental question, whether P= NP.
1.1. THE COMPLEXITY CLASS OF P AND NP
The relationship between the complexity class P and NP is an unsolved question in theoretical computer science.
The relationship between the complexity classes P and NP is studied in computational complexity theory which deals with the resources required to solve a given problem. The resources may be the steps required to solve a problem and space needed for formulation of a solution.
The computational machine in the context is assumed to be deterministic, i.e. it always performs sequential operations, one after another.
Theoretically P class consists of problems that can be solved on a deterministic computational machine in amount of time which assumes polynomial equations in the size of inputs. Mathematically this is measured as order of a problem. For P class this is represented as O (K), where K is a positive integer .We are attempting a solution of order five i.e. O (5).
On the other hand NP class means problems whose solution can only be verified on a deterministic computational machine and can be found only by a Non-deterministic computational machine in polynomial time.
THE CONCEPT OF NP COMPLETENESS
NP complete problems are those problems which are the
‘tough most’ and ‘hardest’ problems in
NP