– The problem presented by the Clay Institute says:
“Suppose that you are organizing housing accommodations for a group of four 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.”
– Remember that Cook-Levin theorem says, in essence, that some problems are easy to formulate but require so many computations that a machine capable of solving them cannot exist.
– We know that no student can be a pair of itself and it is excluded that all students have problems with everyone. Therefore, all students in the IS subset have at least one (or more students) with whom to form a compatible pair. If we use distinction (a set formation process) as a method of reduction and deduction, we will reach to the following conclusion:
– We will call Problematic (PS) the subset of students who belong to the subset of Incompatible pairs (IS) and Non-problematic (NPS) the subset of students who do not belong to the subset of Incompatible pairs (IS). Then, if I have x students en PS, then I have x students in NPS, and then, if it is necessary, I add students of IS in NPS for forming 50 pairs in CS. Then…
PS (NPS +PS +IS) CS (in pairs)
– If 100 → 300 → 0 → 0 → 50
– If 200 → 200 → 0 → 0 → 50
– If 300 → 100 → 0 → 0 → 50
– If 310 → 90 + 10 → 0→ 50
– If 320 → 80 + 20 → 0 → 50
– If 330 → 70 + 30 → 0 → 50
– If 340 → 60 + 40 → 0 → 50
– If 350 → 50 + 50 → 0 → 50
– If 351 → 49 + 49 + (1+1At least one) → 50
– If 352 → 48 + 48 + (2+2Alo) → 50
– If 353 → 47 + 47 + (3+3Alo) → 50
– If 354 → 46 + 46 + (4+4Alo) → 50
– If 355 → 45 + 45 + (5+5Alo) → 50
– If 356 → 44 + 44 + (6+6Alo) → 50
– If 357 → 43 + 43 + (7+7Alo) → 50
– If 358 → 42 + 42 + (8+8Alo) → 50
– If 359 → 41 + 41 + (9+9Alo) → 50
– If 360 → 40 + 40 + (10+10Alo) → 50
– If 370 → 30 + 30 + (20+20Alo) → 50
– If 380 → 20 + 20 + (30+30Alo) → 50
– If 390 → 10 + 10 + (40+40Alo) → 50
– If 400 → 0 + 0 + (50+50Alo) → 50
– The solution until 350 problematic students is easy. Only from 351 to 400 problematic students you have to select (in IS) successively (one by one) x number of students, with their respective at least one, to form 50 compatible pairs.
See A Universal Algorithm For A Hypothetical Machine Learning
Debe estar conectado para enviar un comentario.