استفاده از تجانس برای پیدا کردن نزدیک ترین همسایه در ابعاد بالا

http://aidblab.cse.iitm.ac.in/cs625/6.FastMap.pdf

البته این کار را با روش دیگری امتحان کرده است، شاید با روشی که من می خواهم انجام بدهم کار کند.

مقاله پردازش موازی

مطمئن نیستم ارائه داشته باشیم اما یک مقاله در مورد موضوع مورد علاقه ام پیدا کردم. چون هنوز استاد درس نخواسته اند که موضوع ارائه را مشخص کنیم نمی توانم اینجا چیز بیشتری بنویسم (چون ممکن است یک نفر دیگر این موضوع را انتخاب کند).

یادآوری

به من یادآوری کنید که به استادم یادآوری کنم که به بچه ها یادآوری کنند که سر ارائه ی من بیایند.

به نظرم قسمت های زیادی از موضوع را اشتباه فهمیدم و هر چه بیشتر می خوانم بیشتر گیج می شوم و کمتر می فهمم.

min-wise independent hashing

http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/BroderCFM-minwise.pdf

مرجع هندسه محاسباتی پیشرفته

خودم این را پیدا کرده بودم اما نمی دانم چرا قبلا نگذاشته بودمش.

دریافت
حجم: 409 کیلوبایت

انتشار (broadcast) - موازی

در پست قبل گفتیم که:

راهنمایی حل سوال:

فرض کنید می خواهیم از host داده ای را برای همه ی پردازنده ها broadcast کنیم. با یک bfs از host روی گراف (فعلا یالهای را بدون جهت در نظر می گیریم) می زنیم و یال با وزن 0 اضافه می کنیم. از آنجایی که گراف اولیه systolic بوده است و درخت (bfs) دور ندارد، پس دور با وزن 0 نداریم و گراف جدید semi-systolic است و با روش گفته شده می توانیم آن را systolic کنیم.

ثابت می کنیم که با 2 برابر کردن وزن یالها حتما می توانیم این گراف را systolic کنیم. برای این کار کافی است نشان دهیم که حداکثر نصف یالهای هر دور وزن 0 دارند. = حداکثر نصف یالهای هر دور از درخت bfs آمده اند. هر یال bfs عمق را یکی زیاد می کند و هر یال غیر bfs عمق را حداکثر یکی کم می کند. چون یک دور است باید از همان راسی که شروع کرده به همان برگردد پس تعداد یالهای bfs از غیر bfs کمتر مساوی است.

(تا آخر 1.4.5)

تبدیل مدار semi-systolic به systolic

اگر مداری چیزی را همزمان برای همه ی پردازنده ها بفرستد یا همزمان مقدار تعدادی پردازنده را جمع کند و ... . (خلاصه همزمان یک سری کار روی همه انجام بدهد) دیگر مدار ما systolic نیست. اگر بتوان چنین مداری را به systolic تبدیل کرد به این مدار semi-systolic می گویند و در ادامه شرایط آن و نحوه ی تبدیل آن را نشان می دهیم.

مدار بالا در مدل میلی است (یعنی مقدار خروجی علاوه بر رجیسترها از مدار هم می آید. (خط چین ها از مدار می آیند.)

گراف متناظر آن به صورت زیر است: (همان طور که زیر شکل نوشته شده تعداد بافرها را وزن یالها می گیریم و پردازنده ها راسها هستند.)

اگر گرافی که به دست می آید دور صفر نداشته باشد (دوری که همه ی یالهای آن وزن صفر داشته باشند) می توانیم آن را به systolic تبدیل کنیم.

مرحله اول: همه ی بافرها را چند برابر کنیم، با این کار عملکرد مدار تغییر نمی کند و فقط تاخیر ایجاد می شود. در گراف همه ی یالها در یک عدد ضرب می شوند. عددی را برای این کار انتخاب می کنیم که همه ی دورها وزنشان از تعداد یالهایشان بیشتر یا مساوی باشد؛ که بعدا بتوانیم با ایجاد تاخیر در گره ها یالهای با وزن صفر را از بین ببریم. (چون کلا مشکل ما این است که یک سری کار همزمان با هم دارند انجام می شوند.)

مرحله دوم: با عمل lagging در گره ها تاخیر ایجاد کنیم. (شکل زیر)

می خواهیم ثابت کنیم که هر مداری که این شرط (نبود دور صفر) را داشته باشد (semi-systolic باشد)، می توانیم با یک دنباله از عملیات قبل به یک مدار systolic تبدیل کنیم.

اثبات: اینکه با انجام عملیات lagging شرط semi-systolic بودن به هم نمی خورد تقریبا بدیهی است. می خواهیم ثابت کنیم که حتما با دنباله ای از عملیات lagging می توانیم از S به S' برسیم.

استقرا: پایه استقرا همان حالت اولیه است که با 0 عمل lagging به یک مدار semi-systolic می رسیم (خود S!)

فرض استقرا: برای تعداد توابع lagging کمتر از L مدار semi-systolic بماند.

حکم استقرا: برای L تابع lag مدار semi-systolic است.

اگر گره ای باشد که lag آن مثبت باشد و درجه ی همه ی یالهای خروجی آن ناصفر باشد می توان روی آن یک عمل lag انجام داد. با این کار یکی از تعداد عملیات lag لازم کم می شود و L-1 عمل lag طبق فرض استقرا مدار را semi-systolic می کند.

اگر چنین گره ای نباشد، یعنی همه ی راسهای با lag مثبت یال خروجی صفر دارند. می دانیم با طی هر یال با وزن صفر از یک راس با lag مثبت به راس دیگری با lag مثبت می رسیم، چون اگر یک سر آن وزن یال را کم می کند دیگری باید آن را اضافه کند وگرنه به یال با وزن منفی می رسیم. پس اگر یک راس مثبت یال صفر داشته باشد آن یال به یک راس مثبت دیگر می رود، با دنبال کردن یالهای به وزن صفر خروجی راسهای با lag مثبت یک دور به وجود می آید که وزن آن صفر است که با فرض semi-systolic بودن S (نه S') در تناقض است. (چون ثابت کردیم وزن دورهای S' و S برابرند.)

برای lag منفی هم مشابه همین استدلال را می توانیم انجام بدهیم.

(پایان اثبات)

باید مقادیر رجیسترهایی که جا به جا می کنیم را هم اصلاح کنیم.

حالا می خواهیم تابع lag را به دست بیاوریم.

اثبات:

تابع بالایعنی کوتاهترین مسیر از هر گره تا host در گراف G-1 تابع lag مورد نظر است. ثابت می کنیم این تابع مدار را systolic می کند.

مثال: برای سوال palindrome که در ابتدای متن گفته شد، باید وزن یالهای گراف را در 2 ضرب کنیم شرایط semi-systolic را پیدا می کند و با استفاده از قضیه قبل مدار زیر به دست می آید.

راهنمایی حل سوالات آخر فصل با این روش!

محاسبه وارون ماتریس

در پست های قبلی در مورد وارون ماتریس پایین مثلثی صحبت کردیم. اینجا وارون ماتریس را در حالت کلی با روش مشابه روش حذفی گاوس به دست می آوریم. برای این کار یک ماتریس همانی به انتهای ماتریس اضافه می کنیم و پس از پایان عملیات در سمت چپ (جایی که ابتدا ماتریس ورودی ما بوده است) یک ماتریس همانی خواهد بود و در سمت چپ (که ابتدا یک ماتریس همانی بوده است) وارون ماتریس به دست می آید.

روش حذفی گاوس

می توان با استفاده از نیمه ی بالایی یک مش مساله را حل کرد. دلیل درستی آن این است که ما برای محاسبه ی xi می خواهیم یک سطر مقدار i-امین عنصر آن ناصفر باشد و مقدار بقیه عناصر آن صفر باشد. به دلیل اینکه به محض اینکه سطر مورد نظر را پیدا کردیم xi را حساب می کنیم، ترتیب عناصر به هم نمی خورد. همچنین برای سطرهای قبلی هم مشکلی پیش نمی آید، چون درایه ی iام آنها خود به خود صفر بوده است و نیازی به اینکه ما آن را صفر کنیم نیست.

فصل 2 WS

* زمانبندی کارهای دارای ددلاین روی یک ماشین

هدف این کار می تواند تمام شدن همه ی کارها در کمترین زمان، کم شدن میانگین زمان انجام کار باشد. ما ساده ترین نسخه را حل می کنیم.

مساله: فرض کنید n کار را می خواهیم روی یک ماشین زمانبندی کنیم که هر ماشین در هر زمان می تواند یک کار را پردازش کند و کار را بعد از شروع آن باید تا اتمام آن ادامه دهد. فرض کنید پردازش کار jام از زمان مشخصی زودتر قابل انجام نباشد (r_j). فرض می کنیم زمانبندی در زمان 0 شروع می شود و هر زمان انجامی مثبت است. به علاوه کار jام یک زمان پایان d_j دارد. اگر کار را در زمان Cj تمام کنیم، دیرکرد آن Lj = Cj-dj است، ما می خواهیم کارها را طوری زمانبندی کنیم که L_max را مینیمم کنیم که L_max ماکسیمم دیرکردها (Lj) ها است.

این مساله NP-hard است. حتی نسخه ی تصمیم گیری اینکه L_max < 0 است (= تصمیم گیری اینکه همه کارها می توانند قبل از زمان مهلتشان تمام شوند) هم strongly np-hard است.

ما در زندگی روزمره مان با یک الگوریتم تقریبی ساده این کار را انجام می دهیم: روی کاری با نزدیک ترین مهلت تمرکز کنید. نشان می دهیم که در شرایط خاصی قابل اثبات است که این کار خوبی است. هرچند همان طور که گفته شد جواب نزدیک بهینه (تقریبی) ندارد. اگر یک الگوریتم تقریبی برای آن بود، برای هر مساله با جواب L_max = 0 راه حل تقریبی مساله در حالت کلی برای آن ضریب تقریب * 0 = 0 پس باید برای مساله تمام شدن همه ی کارها قبل از ددلاین یک راه حل بهینه باشد که ممکن نیست مگر اینکه P=NP. برای حالت هایی که L_max مینیمم در آنها منفی شود، کار سخت تر است. یک حالت ساده ی رخ دادن این مشکل این است که فرض کنیم همه ی زمان های پایانی منفی هستند که باعث می شود جواب همیشه مثبت باشد. برای این حالت یک الگوریتم 2-تقریبی می دهیم.

ابتدا یک کران پایین خوب برای جواب بهینه برای مساله زمانبندی می دهیم. فرض کنید S زیرمجموعه ای از کارها باشد و r(S) را مینیمم r_j ها قرار دهید (زمان شروع ها) و p(S) را جمع pjها (زمان پردازش ها) و d(S) را ماکسیمم dj ها (زمان پایان ها). L* جواب بهینه است.

لم: برای هر زیر مجموعه از کارها داریم:

L*_max >= r(S)+p(S)-d(S)

اثبات:

هر کاری در زودترین زمانی که می تواند برسد r(S) است که اگر همه ی کارها پشت سر هم انجام شوند p(S) طول می کشد پس زمان بیشتر از r(S)+p(S) است که از طرفین d(S) را کم می کنیم. (پایان اثبات)

یک کار j در زمان t مجاز است اگر زمان رسیدن r_j از t کمتر مساوی باشد. الگوریتم زیر را در نظر می گیریم: در هر لحظه که ماشین بیکار است، کار در دسترس بعدی که زودترین ددلاین را دارد شروع کن. به این کار earliest due date (EDD) (زودترین مهلت انجام) می گویند.

قضیه: قانون EDD یک الگوریتم 2-تقریبی برای مساله کمینه کردن ماکسیمم تاخیر (L_max) روی یک ماشین با توجه به زمانهای رسیدن و با فرض مهلت پایان های منفی است. {با فرض اینکه مهلت کارها گذشته باشد.}

اثبات: جواب الگوریتم را در نظر بگیرید. فرض کنید j کاری باشد که L_max به ازای آن رخ می دهد. Lmax = Cj-dj. روی زمان Cj بحث می کنیم: اولین زمانی را پیدا کنید t<= Cj که ماشین به ازای آن در کل بازه ی بسته ی t تا باز Cj در حال کار بوده است. چندین کار می توانسته اند در این زمان پردازش شوند. ما فقط کارهایی را که ماشین به ازای آنها مدتی بیکار نباشد لازم داریم. فرض کنید S مجموعه کارهایی باشد که در بازه ی t بسته تا Cj باز پردازش می شوند. با توجه به نحوه انتخاب t، می دانیم که قبل از t هیچ کدام از این کارها در دسترس نبوده اند ( و حتما یک کار در S در زمان t در دسترس بوده است)؛ پس r(S) = t. به علاوه چون تنها کارهای موجود در S در طول این زمان پردازش می شوند: p(S) = Cj-t=Cj-r(S). پس Cj <= r(S)+p(S).

چون d(S) منفی است پس طبق لم قبل:

L*_max >= r(S)+p(S)-d(S) >= r(S)+p(S) >= Cj

با استفاده از همین لم و در نظر گرفتن مجموعه تک عضوی کار j-ام داریم:

L*_max >= rj+pj-dj >= -dj

از جمع دو نامساوی قبل به دست می آید:

2*L*_max >= Cj-dj

Cj-dj = L_max

==> L_max <= 2*L*_max

----------------------------------------------------------------------------------------------------------------------------------------

* زمانبندی کارها روی ماشین های موازی یکسان

نسخه ای از مساله که در آن چند ماشین داریم و هیچ زمان شروعی نداریم، اما هدف ما مینیمم کردن زمانی است که همه ی کارها تمام شوند. فرض کنید n کار باید پردازش شوند، و m ماشین یکسان هستند که به طور موازی کار می کنند و به هر کدام هر کار ممکن است اختصاص داده شود. هر کار باید روی یکی از این ماشینها به مدت pj بدون وقفه اجرا شود و همه ی کارها در زمان 0 در دسترس هستند. هر ماسین می تواند یک کار را در هر زمان انجام دهد. هدف تمام کردن همه ی کارها در زودترین زمان است، یعنی اگر کار j در زمان Cj (با فرض اینکه زمانبندی از 0 شروع شود) تمام شود، می خواهیم C_max را مینیمم کنیم که C_max ماکسیمم C_j ها است. که معمولا makespan یا طول برنامه نامیده می شود. یک دید معادل به مساله، مساله load-balancing است: n چیز داریم که وزن pj دارند و بین m ماشین توزیع شده اند، هدف تخصیص دادن هر چیز به یک ماشین است که ماکسیمم جمع وزن داده شده به یک ماشین را مینیمم کنیم.

این مساله انقدر ساده است که هم جستحو محلی هم حریصانه برای طول برنامه تقریب 2 می دهند.

الگوریتم جستجوی محلی به صورت تغییرات محلی یا حرکت های محلی است که یک جواب ممکن را به یک جواب ممکن دیگر تبدیل می کنند. ساده ترین جستجوی محلی برای این مساله زمانبندی به صورت زیر است: با یک زمانبندی شروع کنید؛ کار j را در نظر بگیرید که آخرین کاری است که تمام می شود، چک کنید که ماشینی وجود دارد که بتوان این کار را به آن داد و زودتر تمام شود. اگر هست، کار j را به آن ماشین بدهید. می توانیم تشخیص دهیم که کار j را به ماشین دیگر منتقل کنیم یا نه، با چک کردن اینکه آیا ماشینی وجود دارد که این کارهایش را زودتر از Cj-pj تمام می کند. {یعنی قبل از شروع کار j توسط ماشین فعلی بیکار شده باشد.} الگوریتم جستجوی محلی این کار را تا زمانی که آخرین کار تمام شده نتواند منتقل شود ادامه می دهد.

برای تحلیل عملکرد این الگوریتم جستجوی محلی، ما ابتدا یک کران پایین روی طول زمانبندی بهینه C*_max می دهیم. چون هر کار باید پردازش شود، داریم:

2.3: C*_max >= max(pi)

از طرف دیگر می دانیم که در کل باید P = sum(pi) واحد پردازش انجام شود و کلا m ماشین داریم. پس میانگین P/m کار به هر ماشین داده می شود، پس ماشینی هست که حداقل به اندازه میانگین کار داشته باشد:

2.4: C*_max >= ( sum(pi) )/m

جوابی که توسط الگوریتم جستجوی محلی تولید شده است را در نظر بگیرید. فرض کنید j کاری باشد که در برنامه نهایی آخرین کاری باشد که انجام می شود؛ پس زمان اتمام کار j یعنی Cj جواب مساله است. چون الگوریتم با کار j-ام پایان یافته است، پس همه ی پردازنده های دیگر باید از شروع زمان (0) تا زمان شروع کار j-ام مشغول باشند. Sj = Cj-pj (زمان شروع کار j). می توانیم زمانبندی را به دو بازه ی زمانی مجزا تقسیم کنیم، یکی از 0 تا شروع j یعنی Sj و دیگری از آن زمان تا پایان کل برنامه. طبق نامساوی 2.3 بازه ی دوم اندازه ی حداکثر C*_max دارد. حالا بازه ی اول را در نظر بگیرید، چون همه ی ماشین ها در این زمان مشغول هستند پس m*Sj زمان کار در این بازه انجام شده است که بدیهی است از کل کاری که باید انجام شود یعنی sum(pi) ها کمتر است. پس:

2.5: Sj <= (sum(pi) / m)

با ترکیب این نامساوی و نامساوی 2.4 به دست می آید:

Sj <= C*_max

پس، طول برنامه قبل از شروع کار j حداکثر C*_max بوده است و طول آن بعد از انجام کار هم همین قدر است، پس طول برنامه ی الگوریتم حداکثر دو برابر جواب بهینه (2C*_max) است.

حالا زمان اجرای این الگوریتم را در نظر بگیرید. این جستجوی محلی این خاصیت را دارد که دنباله ی C_max های تولید شده در آن هیچ گاه نزولی نیست ( می تواند ثابت باشد اما در این صورت تعداد ماشین هایی که به مقدار زمان بیشینه می رسند کاهش می یابد). یک فرض طبیعی این است که وقتی کاری را به یک ماشین دیگر می دهیم، آن را به ماشینی بدهیم که در حال حاضر زودتر از همه کارش را تمام می کند. ما زمان اجرای این نسخه را به جای قبلی به دست می آوریم. فرض کنید C_min زمان اتمام ماشینی باشد که زودتر از همه کارهایش را تمام می کند. یک نتیجه ی تمرکز روی این نسخه این است که C_min هیچ گاه کم نمی شود (و اگر همان قدر بماند، تعداد ماشینهایی که این کمترین مقدار را به دست می آورند کاهش می یابد). در ادامه نشان می دهیم که این نتیجه می دهد که ما هیچ وقت یک کار را دو بار جا به جا نمی کنیم. فرض کنید این ادعا درست نباشد، اولین کار j را که دو بار جا به جا شده است در نظر بگیرید، فرض کنید از ماشین i به ماشین i' و بعد از آن به i*. وقتی کار j از ماشین i به i' منتقل می شود، در زمان Cmin برنامه فعلی شروع می شود. به طور مشابه وقتی کار j از i' به i* منتقل می شود، در زمان C'_min شروع می شود. به علاوه هیچ تغییری روی ماشین i' در بین این دو انتقل رخ نداده اشت. پس C'_min باید اکیدا کمتر از C_min باشد (تا انتقال یک عمل بهبود دهنده باشد) اما این با ادعای C_min در طول اجرای الگوریتم جستجوی محلی غیر نزولی است متناقض است. پس هیچ کاری دو بار منتقل نشده است و بعد از حداکثر n گام، الگوریتم متوقف می شود. پس ما قضیه زیر را ثابت کردیم:

قضیه 2.5: الگوریتم جستجوی محلی برای زمانبندی کارها روی ماشین های موازی یکسان یک الگوریتم 2-تقریبی است.

تحلیل ضریب تقریب می تواند کمی بهبد یابد. در به دست آوردن نامساوی 2.5، کار j را بین کارهایی که قبل از شروع کار j تمام می شوند حساب کرده ایم. پس می توانیم به دست بیاوریم:

Sj <= (sum( pi) -pj) / m

==> total length <= pj+(sum(pi)-pj)/m = (1-1/m)pj+sum(pi) /m

با اعمال دو کران پاینن 2.3 و 2.4 روی دو جمله بالا می توانیم نشان دهیم که طول برنامه حداکثر 

(2-1/m)C*_max

است. البته تفاوت بین این کران و 2 تنها وقتی مهم است که تعداد ماشینها خیلی کم باشد.

-----

الگوریتم طبیعی دیگری که برای محاسبه برنامه است الگوریتم حریصانه ای است که هر کار را به محض اینکه یک ماشین بیکار شد به آن اختصاص می دهد. این الگوریتم معمولا list scheduling algorithm نامیده می شود، چون می توان الگوریتم را به صورت مرتب کردن کارها در یک لیست به ترتیب دلخواه دید که کار بعدی که انجام می شود کار سر لیست است. یک دید دیگر، از دیدگاه load-balancing است که کار بعدی لیست به ماشینی که الآن کمترین بار را دارد اختصاص داده شود. در این حالت است که الگوریتم می تواند به صورت حریصانه دیده شود. تحلیل این الگوریتم اکنون بدیهی است؛ اگر کسی از این برنامه به عنوان نقطه شروع جستجوی محلی استفاده کند، الگوریتم همان موقع اعلام می کند که زمانبندی نمی تواند بهبود داده شود. برای فهمیدن این موضوع، کار j را که یکی از کارهاست که آخرین کاری است که اجرایش تمام می شود، در نظر بگیرید. هر ماشینی تا زمان Cj-pj مشغول است، چون در غیر این صورت به آن کار j را اختصاص می دادیم. پس هیچ انتقالی امکان پذیر نیست.

قضیه 2.6: الگوریتم list scheduling برای مساله کمینه کردن طول برنامه با داشتن m ماشین یکسان موازی 2-تقریبی است.

به دست آوردن نتیجه بهتر با بهبود این الگوریتم سخت نیست. همه ی لیست ها یک برنامه را نمی دهند و طبیعی است که از قانون حریصانه ی اضافی استفاده کنیم که ابتدا کارها را به صورت غیر صعودی مرتب می کند. {نزولی غیر اکید}. یک راه برای دیدن نتیجه قضیه 2.5 و 2.6 این است که خطای نسبی طول برنامه کاملا مربوط به آخرین کار انجام شده است. پس اگر کار کوتاهی انجام شود، خطا خیلی بزرگ نمی شود. این الگوریتم حریصانه longest processing time یا به اختصار LPT نامیده می شود.

قضیه 2.7: LPT یک الگوریتم 4/3-تقریبی برای زمانبندی کارها برای مینمم کردن طول برنامه روی ماشین های موازی یکسان است.

اثبات: برهان خلف: فرض کنید یک ورودی مثال نقضی برای قضیه باشد. برای سادگی نگارش فرض کنید p1>= ...>= pn باشد. ابتدا می توانیم فرض کنیم که آخرین کاری که انجام می شود آخرین (کوتاهترین) کار در لیست است. این نتیجه می دهد (بدون از دست رفتن عمومیت مساله) که هر مثال نقضی که آخرین کار آن کوتاهترین کار نباشد و کار j-ام باشد، می توانیم ثابت کنیم که غلط است، چون کارهای j+1,...,n راحذف می کنیم، طول برنامه همان می ماند و جواب بهینه ورودی کاهش یافته نمی تواند بزرگتر باشد. پس این ورودی کاهش یافته هم یک مثال نقض است.

پس می دانیم که آخرین کاری که کامل می شود کار nام است. اگر این یک مثال نقض باشد، ما در مورد pn=pj چه می دانیم؟ اگر pj <= C*_max باشد، تحلیل قضیه 2.6 نتیجه می دهد که طول برنامه حداکثر (4/3)C*_max است و درنتیجه این یک مثال نقض نیست. پس می دانیم که در این مثال نقض فرضی، کار n ام (و در نتیجه همه کارها) زمان پردازش اکیداً بیشتر از 1/3C*_max دارند. این نتیجه ی ساده ی زیر را دارد:

در زمانبندی بهینه، هر ماشین می تواند حداکثر دو کار را پردازش کند (چون در غیر این صورت زمان پردازش آن از C*_max بیشتر می شود).

اینجا مثال نقض فرض مان به جایی رسیده است که وجود آن امکان پذیر نیست. برای ورودی های دارای این ساختار، لم بعد را به کار می بریم.

لم 2.8: برای هر ورودی مساله مینیمم کردن زمان روی ماشین های موازی یکسان که در آن نیازمندی های هر کار از 1/3 طول زمان مورد نیاز بیشتر است، longest processing time (LPT) جواب بهینه را به دست می آورد.

این لم می تواند با استفاده از چک کردن حالت ها انجام شود (تمرین 2.2). هر چند نتیجه این لم مشخص است: هیچ مثال نقضی برای این قضیه وجود ندارد پس برقرار است.

در قسمت 3.2 نشان می دهیم که می توان برای این مساله الگوریتم تقریبی با زمان چندجمله ای ارائه داد.