Problem of the Millennium: P vs NP Problem I (Second part)

Problem of the Millennium: P vs NP Problem I

(Second part)

by

Lutvo Kurić

Independent researcher - Bosnia and Herzegovina,

72290 Novi Travnik, Kalinska 7.

Tel. 061 763 917

lutvokuric@yahoo.com

Determinant 1

X1	X2
		=	R
X3	X4

X1=376; X2=25; X3=375; X4=26;

R = 401;

X1,2,3,4 = Students on the list appear in our final choice.

Determinant 2

X5	X6
		=	R
X7	X8

X1=377; X2=24; X3=374; X4=27;

R = 1203;

1203 = (401+401+401+401)

Determinant 3

X9	X10
		=	R
X11	X12

X1=378; X2=23; X3=373; X4=28;

R = 2005;

2005 = (401+401+401+401+401)

etc.

Determinants(A)

	Pairs of students			Pairs of students		DET
376		25	375		26	(376,25,375,26) = 401 = (401 x 01)
377		24	374		27	(377,24,374,27) = 1203 = (401 x 03)
378		23	373		28	(378,23,373,28) = 2005 = (401 x 05)
379		22	372		29	(379,22,372,29) = 2807 = (401 x 07)
380		21	371		30	(380,21,371,30) = 3609 = (401 x 09)
381		20	370		31	(381,20,370,31) = 4411 = (401 x 11)
382		19	369		32	(382,19,369,32) = 5213 = (401 x 13)
383		18	368		33	(383,18,368,33) = 6015 = (401 x 15)
384		17	367		34	(384,17,367,34) = 6817 = (401 x 17)
385		16	366		35	(385,16,366,36) = 7619 = (401 x 19)
386		15	365		36	(386,15,365,36) = 8421 = (401 x 21)
387		14	364		37	(387,14,364,37) = 9223 = (401 x 23)
388		13	363		38	(388,13,363,38) = 10025 = (401 x 25)
389		12	362		39	(389,12,362,39) = 10827 = (401 x 27)
390		11	361		40	(390,11,361,40) = 11629 = (401 x 29)
391		10	360		41	(391,10,360,41) = 12431 = (401 x 31)
392		9	359		42	(392,09,359,42) = 13233 = (401 x 33)
393		8	358		43	(393,08,358,43) = 14035 = (401 x 35)
394		7	357		44	(394,07,357,44) = 14837 = (401 x 37)
395		6	356		45	(395,06,356,45) = 15639 = (401 x 39)
396		5	355		46	(396,05,355,46) = 16441 = (401 x 41)
397		4	354		47	(397,04,354,47) = 17243 = (401 x 43)
398		3	353		48	(398,03,353,48) = 18045 = (401 x 45)
399		2	352		49	(399,02,352,49) = 18847 = (401 x 47)
400		1	351		50	(400,01,351,50) = 19649 = (401 x 49)

Determinants(B)

	Pairs of students			Pairs of students		DET
301		100	250		151	(301,100,250,151) = 20 451 = (401 x 051)
302		99	249		152	(302,099,249,152) = 21 253 = (401 x 053)
303		98	248		153	(303,098,248,153) = 22 055 = (401 x 055)
304		97	247		154	(304,097,247,154) = 22 857 = (401 x 057)
305		96	246		155	(305,096,246,155) = 23659 = (401 x 059)
306		95	245		156	(306,095,245,156) = 24 461 = (401 x 061)
307		94	244		157	(307,094,244,157) = 25 263 = (401 x 063)
308		93	243		158	(308,093,243,158) = 26 065 = (401 x 065)
309		92	242		159	(309,092,242,159) = 26 867 = (401 x 067)
310		91	241		160	(310,091,241,160) = 27 669 = (401 x 069)
311		90	240		161	(311,090,240,161) = 28 471 = (401 x 071)
312		89	239		162	(312,089,239,162) = 29 273 = (401 x 073)
313		88	238		163	(313,088,238,163) = 30 075 = (401 x 075)
314		87	237		164	(314,087,237, 164) = 30 877 = (401 x 077)
315		86	236		165	(315,086,236,165) = 31 679 = (401 x 079)
316		85	235		166	(316,085,235,166) = 32 481 = (401 x 081)
317		84	234		167	(317,084,234,167) = 33 283 = (401 x 083)
318		83	233		168	(318,083,233,168) = 34 085 = (401 x 085)
319		82	232		169	(319,082,232,169) = 34 887 = (401 x 087)
320		81	231		170	(320,081,231,170) = 35 689 = (401 x 089)
321		80	230		171	(321,080,230,171) = 36 491 = (401 x 091)
322		79	229		172	(322,079,229,172) = 37 293 = (401 x 093)
323		78	228		173	(323,078,228,173) = 38 095 = (401 x 095)
324		77	227		174	(324,077,227,174) = 38 897 = (401 x 097)
325		76	226		175	(325,076,226,175) = 39 699 = (401 x 099)
326		75	225		176	(326,075,225,176) = 40501 = (401 x 101)
327		74	224		177	(327,074,224,177) = 41303 = (401 x 103)
328		73	223		178	(328,073,223,178) = 42105 = (401 x 105)
329		72	222		179	(329,072,222,179) = 42907 = (401 x 107)
330		71	221		180	(330,071,221,180) = 43709 = (401 x 109)
331		70	220		181	(331,070,220,181) = 44511 = (401 x 111)
332		69	219		182	(332,069,219,182) = 45313 = (401 x 113)
333		68	218		183	(333,068,218,183) = 46115 = (401 x 115)
334		67	217		184	(334,067,217,184) = 46917 = (401 x 117)
335		66	216		185	(335,066,216,186) = 47719 = (401 x 119)
336		65	215		186	(336,065,215,186) = 48521 = (401 x 121)
337		64	214		187	(337,064,214,187) = 49323 = (401 x 123)
338		63	213		188	(338,063,213,188) = 50125 = (401 x 125)
339		62	212		189	(339,062,212,189) = 50927 = (401 x 127)
340		61	211		190	(340,061,211,190) = 51729 = (401 x 129)
341		60	210		191	(341,060,210,191) = 52531 = (401 x 131)
342		59	209		192	(342,059,209,192) = 53333 = (401 x 133)
343		58	208		193	(343,058,208,193) = 54135 = (401 x 135)
344		57	207		194	(344,057,207,194) = 54937 = (401 x 137)
345		56	206		195	(345,056,206,195) = 55739 = (401 x 139)
346		55	205		196	(346,055,205,196) = 56541 = (401 x 141)
347		54	204		197	(347,054,204,197) = 57343 = (401 x 143)
348		53	203		198	(348,053,203,198) = 58145 = (401 x 145)
349		52	202		199	(349,052,202,199) = 58947 = (401 x 147)
350		51	201		200	(350,051,201,200) =59749 = (401 x 149)

List appear in our final choice

	Pairs of students		Sum			Pairs of students		Sum
1		400	401		26		375	401
2		399	401		27		374	401
3		398	401		28		373	401
4		397	401		29		372	401
5		396	401		30		371	401
6		395	401		31		370	401
7		394	401		32		369	401
8		393	401		33		368	401
9		392	401		34		367	401
10		391	401		35		366	401
11		390	401		36		365	401
12		389	401		37		364	401
13		388	401		38		363	401
14		387	401		39		362	401
15		386	401		40		361	401
16		385	401		41		360	401
17		384	401		42		359	401
18		383	401		43		358	401
19		382	401		44		357	401
20		381	401		45		356	401
21		380	401		46		355	401
22		379	401		47		354	401
23		378	401		48		353	401
24		377	401		49		352	401
25		376	401		50		351	401
Sum		-	-					20050

Example 2

A problem is assigned to the NP (nondeterministic polynomial time) class if it is solvable in polynomial time by a groups of university students. Input code in those groups are code 401.

Gs = 400 university students; SumGs = (1+2+3…, + 400) = 80 200;

Groups with 2 university students

(1+2); (2+3); (3+4);…, (399+400);

G2(1) = (1+2); G2(2) = (2+3); G2(3) = (3+4), etc.

Groups with 3 university students

(1+2+3); (2+3+4); (3+4+5);…, (398+399+400);

G3(1) = (1+2+3); G3(2) = (2+3+4); G3(3) = (3+4+5);

etc.

Formula

í[G3(1,2,3,n) : 1,2,3,n] : 1,2,3,ný = DET (A1,2,3,n)

Example 1

G3 = [(G3(1) + G3(2) + G3(3)…, + G3(n)] = Y;

G3(1) = (1+2+3); G3(2) = (2+3+4); G3(3) = ((3+4+5); G3(4) = (4+5+6);

G3(5) = (5+6+7); G3(6) = (6+7+8);…, G3(49) = (49+50 + 351);

G3(50) = (50+351+352); G3(51) = (351+352+353);…, G3(398) = (398+399+400);

Y = 58 947;

G3 = 58 947;

19649 = (49 x 401);

Determinants 49

400	001
		=	19 649
351	050

400, 001, 351, 050 = Students on the list appear in our final choice.

Example 2

G7 = [(G7(1) + G7(2) + G7(3)…, + G7(n)] = Y;

G7(1) = (1+2+3+4+5+6+7); G7(2) = (2+3+4+5+6+7+8); G7(3) = ((3+4+5+6+7+8+9); G7(4) = (4+5+6+7+8+9+10)…, G7(44) = (44+45+46+47+48+49+50); G7(45) = (45+46+47+48+49+50+ 351); …, G7(351) = (351+352+353)+354+355+356+357);…, G7(394) = (394+395+396+397+398+399+400);

Y = 131 929;

G7 = 131 929;

18847 = (47 x 401);

Determinant 47

399	002
		=	18 847
352	049

399, 008, 252, 049 = Students on the list appear in our final choice.

Example 3

G11 = [(G11(1) + 11(2) + G11(3)…, + G11(n)] = Y;

G11(1) = (1+2+3+4+5+6+7+8+9+10+11); G11(2) = (2+3+4+5+6+7+8+9+10+11+12); G11(3) = ((3+4+5+6+7+8+9+10+11+12+13); …,G11(50) = (50+351+352+353+354+ +355+356+357+358+359+360);…,

G11(390) = (390+391+392+393+394+395+396+397+398+399+400);

Y = 198 495;

G11 = 198 495;

18045 = (45 x 401);

Determinant 45

398	003
		=	18 045
353	048

398, 003, 353, 048 = Students on the list appear in our final choice.

etc.

Resume

A problem is assigned to the NP (nondeterministic polynomial time) class if it is solvable in polynomial time by a groups numbers and determinants 2x2.

References

1)A problem is assigned to the NP (nondeterministic polynomial time) class if it is solvable in polynomial time by a nondeterministic Turing machine.

2)A P-problem (whose solution time is bounded by a polynomial) is always also NP. If a problem is known to be NP, and a solution to the problem is somehow known, then demonstrating the correctness of the solution can always be reduced to a single P (polynomial time) verification. If P and NP are not equivalent, then the solution of NP-problems requires (in the worst case) an exhaustive search.

3)Linear programming, long known to be NP and thought not to be P, was shown to be P by L. Khachian in 1979. It is an important unsolved problem to determine if all apparently NP problems are actually P.

4)A problem is said to be NP-hard if an algorithm for solving it can be translated into one for solving any other NP-problem. It is much easier to show that a problem is NP than to show that it is NP-hard. A problem which is both NP and NP-hard is called an NP-complete problem.