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

Problem of the Millennium: P vs NP Problem I

by

Lutvo Kurić

Independent researcher - Bosnia and Herzegovina,

72290 Novi Travnik, Kalinska 7.

Tel. 061 763 917

lutvokuric@yahoo.com

Suppose that you are organizing housing accommodations for a group of 4 hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair from taken from your coworker's list also appears on the list from the Dean's

We begin by describing the generalization of this problem.

Example 1

Formula 1

(Gs : SumGs) = (Km : SumKm)

Gs = 400 university students; SumGs = (1+2+3…, + 400) = 80 200; Km = One hundred of the students will receive places in the dormitory. SumKM = (1+2+3…, + 100) = 20 050;

(400 : 80 200) = (100 : 20 050)

(400 x 20 050) = (80 200 x 100);

Formula 2

NP : SumNP = Km : SumKm

NP = 300 incompatible students,

SumNP = (1+2+3…, + 300) = 60 150; (300 : 60 150) = (100 : 20 050); (300 x 20 050) = (60 150 x 100);

Formula 3

Gs : SumGs = NP : SumNP

(400 : 80 200) = (300 : 60 150); (400 x 60 150) = (80 200 x 300);

etc.

Determinants

A problem is assigned to the NP (nondeterministic polynomial time) class if it is solvable in polynomial time by a determinants 2x2. Input code in those determinants are code 401.

X1	X2
		=	R
X3	X4

X1,2,3,n = Number of place in the dormitory

Code 401 (1)

	Pairs		Sum			Pairs		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

Code 401 (2)

	PAIRS		Sum			PAIRS		Sum			PAIRS		Sum
51		350	401		101		300	401		151		250	401
52		349	401		102		299	401		152		249	401
53		348	401		103		298	401		153		248	401
54		347	401		104		297	401		154		247	401
55		346	401		105		296	401		155		246	401
56		345	401		106		295	401		156		245	401
57		344	401		107		294	401		157		244	401
58		343	401		108		293	401		158		243	401
59		342	401		109		292	401		159		242	401
60		341	401		110		291	401		160		241	401
61		340	401		111		290	401		161		240	401
62		339	401		112		289	401		162		239	401
63		338	401		113		288	401		163		238	401
64		337	401		114		287	401		164		237	401
65		336	401		115		286	401		165		236	401
66		335	401		116		285	401		166		235	401
67		334	401		117		284	401		167		234	401
68		333	401		118		283	401		168		233	401
69		332	401		119		282	401		169		232	401
70		331	401		120		281	401		170		231	401
71		330	401		121		280	401		171		230	401
72		329	401		122		279	401		172		229	401
73		328	401		123		278	401		173		228	401
74		327	401		124		277	401		174		227	401
75		326	401		125		276	401		175		226	401
76		325	401		126		275	401		176		225	401
77		324	401		127		274	401		177		224	401
78		323	401		128		273	401		178		223	401
79		322	401		129		272	401		179		222	401
80		321	401		130		271	401		180		221	401
81		320	401		131		270	401		181		220	401
82		319	401		132		269	401		182		219	401
83		318	401		133		268	401		183		218	401
84		317	401		134		267	401		184		217	401
85		316	401		135		266	401		185		216	401
86		315	401		136		265	401		186		215	401
87		314	401		137		264	401		187		214	401
88		313	401		138		263	401		188		213	401
89		312	401		139		262	401		189		212	401
90		311	401		140		261	401		190		211	401
91		310	401		141		260	401		191		210	401
92		309	401		142		259	401		192		209	401
93		308	401		143		258	401		193		208	401
94		307	401		144		257	401		194		207	401
95		306	401		145		256	401		195		206	401
96		305	401		146		255	401		196		205	401
97		304	401		147		254	401		197		204	401
98		303	401		148		253	401		198		203	401
99		302	401		149		252	401		199		202	401
100		301	401		150		251	401		200		201	401
Sum		-	-		-		-	-					60150