||V{maketoc}||
^@#16:
!لئونید لوین: سنت کولموگوروف
هنگامی که کوک در دهه 1960 در هاروارد، سخت درگیر نظریه پیچیدگی بود، یک دانش‌آموز جواب در اتحاد جماهیر شوروی سرگرم یادگیری perebor و پیچیدگی کولموگوروف بود.
لئونید لوین در سال 1948 در شهر دنپروپتروسک که یک شهر صنعتی در مرکز اوکراین بود به دنیا آمد. پدرش آنتونی لوین، ابتدا آموزگار زبان و ادبیات روسی در دبیرستان بود و سپس با اخذ درجه دکتری در تعلیم و تربیت، به تدریس دانشگاه پرداخت. مادر لئونید، مهندس معمار بود و به طراحی پلها می‌پرداخت. لوین از همان ابتدا به ریاضیات و علوم علاقه‌مند شد.
«هنگامی که جدول مندلیف (جدول تناوبی عناصر) را یاد گرفتم، تا حدودی سرخورده و دلسرد شدم، زیرا به نظم و ترتیبی که انتظار داشتم نبود. زمان زیادی صرف کردم و آن را بارها و بارها بازنویسی کردم. نتیجه کار من تقریباً نزدیک به آن چیزی بود که بعدها در آمریکا دیدم.»
لوین به آزمایشهای شیمیایی نیز علاقه‌مند بود و بارها از وان حمام منزل یکی از اقوامش برای ترکیب عناصر شیمیایی استفاده می‌کرد. پدرش برای او یک سری از کتابهایی که توسط یاکوف پارلمان، نویسنده علمی معروف روسف نوشته شده بود را خریداری کرده بود و نیز او را تشویق می‌کرد تا در المپیادهای علمی شرکت کند. این المپیادها توسط دولت شوروی برای کشف دانش‌آموزان با استعداد در زمینه‌های ریاضیات و علوم ترتیب یافته بود. برندگان این مسابقه ابتدا از سطح محلی به سطح منطقه‌ای و بعد کشوری می‌رفتند و سپس برای ورود به مدارس ویژه در زمینه‌های مختلف علوم برگزیده می‌شدند.
«به طور کلی در اواخر دهه 50 و اوایل دهه 60 در روسیه، اشتیاق عمومی زیادی به علوم وجود داشت. المپیادها بسیار محبوبیت داشتند و اغلب بچه‌ها در سراسر کشور در آنها شرکت می‌کردند و اگر کسی در آن برنده می‌شد و ضمناً یهودی هم نبود می‌توانست در مسابقات المپیاد بین‌المللی شرکت کند.»
لوین در المپیاد فیزیکی شهر کیف به مقام نخست رسید و به مدرسه ویژه فیزیک و ریاضیات در دانشگاه کیف فرستاده شد. یکروز، طی مراسم با شکوه و احترام برانگیزی، کولموگوروف از این مدرسه بازدید کرد. لوین در آن هنگام پانزده ساله بود.
«بازدید کولموگوروف از مدرسه ما رویداد بسیار مهمی بود. او ابتدا ما مدیران و آموزگاران و سپس با بچه‌ها ملاقات کرد. در یک اتاق بزرگ، همه ما جمع شده بودیم. او برای ما کمی صحبت کرد و سپس مساله‌ای را مطرح ساخت و از ما خواست که هر کس جوابش را می‌داند دستش را بلند کند و این کار را چند نوبت تکرار کرد و به زودی بین من و یکی از بچه‌ها رقابت برای پاسخ دادن به سوالات در گرفت.»
مسائلی که کولموگوروف برای لوین جوان مطرح کرد، آمادگی خوبی بود برای مسائلی که بعداً در علوم رایانه با آنها مواجه شد. برای نمونه، یکی از راه‌حلهای لوین در داخل کادر به طور جداگانه آورده شده است.
کولموگوروف، توانایی لوین در پاسخگویی به معماها را از یاد نبرد و بعداً او را به مدرسه خود در دانشگاه مسکو دعوت کرد.
«او به گروه کوچکی شامل 20 دانش‌آموز درس می‌داد. او برای ما کنسرت موسیقی ترتیب می‌داد و اشعار شاعران بزرگ را معنی می‌کرد. او خیلی چیزها می‌دانست و در بسیاری از زمینه ها معلوماتی در سطح حرفه‌ای داشت.
کولموگوروف ابتدا به عنوان یک تاریخدان آغاز به کار کرد و فکر می‌کنم خود او در جایی این مطلب را اظهار داشت که بعضی فرضیات را اثبات کرده و نتایج کارش را ارائه نموده ولی به او گفته بودند که کارش عالی است ولی هنوز به اثباتهای بیشتری نیاز می‌باشد. به این دلیل او تصمیم گرفت، که ریاضیدان شود زیرا در این حوزه، یک اثبات برای یک فرضیه کافی است و به اثباتهای بیشتر نیازی نیست.»
لوین خود را غرق در ریاضیات ساخت و تقریباً تمام چیزهای دیگر را کنار گذاشت. او گاه گاهی شطرنج نیز بازی می‌کرد:
«من به داستانهای روسی علاقه‌مند بودم. حافظه‌ای قوی داشتم و اشعار بسیار زیادی را برای تقویت حافظه‌ام حفظ می‌کردم. بعداً این کار را کنار گذاشتم زیرا ترسیدم باعث محدود شدن قدرت تخیلم گردد.»
با وجودی که سیستم شوروی دانشمندان زیادی در ریاضیات و فیزیک پرورش می‌داد اما در زمینه علوم رایانه وضع به گونه‌ای دیگر بود:
«در اوایل دهه پنجاه، علوم رایانه تقریباً موضوعی غیرقانونی در اتحاد جماهیر شوروی بود. در آن زمان همه چیز باید با آموزه‌های مارکس سازگار می‌بود.
من فکر می‌کنم بعضی از فیلسوفان شوروی از دست نوربرت وینر عصبانی شده بودند. وینر در جوانی ریاضیدان بزرگی بود ولی در سنین پیری، مطالب بیربط و چرندی در مورد علوم رایانه نوشت.یکی از ایده‌های «به اصطلاح علمی» او در دوران پیری، سایبرنتیک بود که در شوروی تلقی علوم رایانه از آن می‌شد. هر چند این تلقی کاملاً بیربط و بی‌معنی بود اما فیلسوفان شوروی آن را مخالف مارکسیسم تشخیص داده بودند.»
در دهه 1960، ارتش شوروی به دلیل کاربردهای کاملاً مشهود علوم رایانه، اصرار به تدریس این رشته در دانشگاهها داشت. خود آنها در این مزینه پیشقدم شدند و شروع به آموزش استفاده از رایانه به دانشجویان جوان کردند و نخستین برخورد لوین با رایانه نیز هنگامی روی داد که او در حال گذراندن دوره آموزش نظامی بود. دوره‌ای که تمام دانشجویان باید در آن شرکت می‌کردند.
«ما با یک رایانه خیلی قدیمی کار می‌کردیم ولی برای من بسیار جالب بود. به علاوه، برخی چیزها در ارتباط با نظریه احتمالات را نیز به ما یاد می‌دادند. مثلاً‌ این که موشکی به هوا پرتاب می‌شود چقدر احتمال دارد به این هدف یا آن هدف اصابت کند؟
البته من از ارتش و نظامیگری نفرت داشتم. ولی ریاضیاتی که در آنجا به ما یاد داده می‌شود جالبتر از بسیاری از درسهای دانشگاهی ما از جمله درس آموزش زبان الگول بود که فقط به آموزش قواعد نحوی این زبان برنامه‌نویسی اختصاص داشت.»
---
!راه حل لوین برای معمای کولموگوروف
!!سوال
فرض کنید تمام کلمات، یا دنباله نویسه‌ها، به یکی از دو رده زیر تعلق داشته باشند: کلمات قابل چاپ (خوب) و کلمات غیرقابل چاپ (بد). حال فرض کنید که دنباله‌ای نامتناهی از نویسه‌ها داده شده است. آیا همواره می‌توان ان را به تعدادی زیر دنباله متناهی تقسیم کرد به طوری که احتمالاً بجز اولین زیر دنباله، بقیه به یکی از دو رده فوق تعلق داشته باشند؟
#@
@#16:
__جواب__
بله. برای اثبات دنباله‌ای تعریف می‌کنیم که تمام قسمتهیا اولیه آن «خوب» باشد. چنین دنباله‌ای را «با پیشوند خوب» می‌نامیم. حال دنباله نامتناهی را در نظر می‌گیریم و فرض می‌کنیم یک n محدود وجود دارد که با برداشتن تعدادی نویسه‌ بیشتر از n از ابتدای A، دنباله نامتناهی باقیمانده «بدون پیشوند خوب» گردد. حال 1 + n نویسه از ابتدای A برمی‌داریم. طبق فرض، دنباله نامتناهی باقیمانده، دارای «پیشوند بد» خواهد بود. این پیشوند را بر می‌داریم و با تکرار این عمل به طور نامتناهی بر روی باقیمانده A، دنباله A به تعدادی زیر دنباله متناهی تقسیم می‌شود که تمام آنها بجز اولی که ممکن است «خوب» یا «بد» باشد، غیرقابل چاپ یا «بد» هستند. برای این که ببینیم این عمل به صورت نامتناهی می‌تواند انجام شود،‌ فرض کنید که نتوانیم آن را به تعداد نامتناهی انجام دهیم و بعد از K‌ بار تکرار به دنباله‌ای برسیم که تمام پیشوندهای آن «خوب» باشند که این با فرض وجود n تناقض دارد.
حال فرض کنید عددی مثل n وجود ندارد که با قطع تعدادی نویسه بیشتر از n از ابتدای A، دنباله نامتناهی باقیمانده دارای «پیشوند بد» شود. این عمل را می‌توانید به طور نامتناهی تکرار کنید زیرا در غیر این‌صورت با ترکیب نویسه‌های قطع شده، پیشوندی به طول n به دست می‌آید که با قطع آن از دنباله، باقیمانده دنباله دارای «پیشوند بد» می‌شود که با فرض عدم وجود چنین n تناقض دارد.
حال با تکرار این عمل به صورت نامتناهی، دنباله A به تعدادی زیردنباله متناهی تقسیم می‌شود که بجز اولی که امکان دارد قابل چاپ (خوب) یا غیرقابل چاپ (بد) باشد، بقیه «خوب» هستند چون تمام آنها پیشوندهای یک دنباله «با پیشوند خوب» بوده‌اند.
---
!پیچیدگی کولموگوروف
لوین در سال 1971 برای تز دکتریش به تحقیق در زمینه پیچیدگی کولموگوروف پرداخت. خود کولموگوروف به عنوان استاد راهنما و نیز کمیته‌ای شامل چند ریاضیدانان برجسته دیگر، تز او را قبول کردند ولی با این وجود، لوین از دریافت عنوان دکتری محروم شد. خود او در این باره می‌گوید:
«در آن زمان، تقریباً تمامی جوانان شوروی عضو کامسومول بودند. کامسومول، سازمانی شبیه حزب کمونیست برای جوانان بود. در آنجا از طریق فعالیتهای مختلف به ما یاد داده می‌شد که به دولت عشق بورزیم. من در بعضی از این فعالیتها، کارشکنی و خرابکاری کردم.
البته برای کارهایی که من کردم تنبیهاتی پیش‌بینی شده بود ولی این کار برای آنها نیز بد بود زیرا به بالادستهایشان نشان می‌داد که اشکالاتی در کار وجود دارد. بنابراین آنها تصمیم گرفتند وانمود کنند که اتفاقی نیافتاده است و من از خطر جستم.
ولی کار به همین جا خاتمه نیافت و موضوع به گوش مقامات کمونیست دانشگاه رسید. در نتیجه، نه تنها مرا از اخذ درجه دکتری محروم کردند بلکه در یک بیانیه رسمی، سرشار از کلمات و عبارات سیاسی، مرا از تلاش دوباره برای اخذ دکتری نیز محروم نمودند. و این کار سرانجام باعث مهاجرت من از کشورم شد.»
لوین در سال 1973 و قبل از مهاجرت به آمریکا، مقاله‌ای در یک مجله علمی شوروی درباره مسائل جستجوی دنباله‌ای به چاپ رساند. او در این مقاله، ارتباط بین مسائل perebor و نظریه اطلاعات کولموگوروف را تشریح کرد. در نظریه اطلاعات کولموگوروف، رابطه بین «تصادفی بودن» دنباله‌ای از نویسه‌ها (مثلاً صفرها و یکها) و طول توضیحات راجع به آن، مشخص شده است. به عنوان مثال، به راحتی می‌توان رشته‌ای از یک میلیون عدد یک متوالی را در چند کلمه تشریح کرد. (همین‌کاری که اکنون ما کردیم.) به طور مشابه، هر الگوی تکراری را نیز می‌توان در جملات کوتاهی توصیف کرد. مثلاً‌ اگر 00111 یک میلیون بار تکرار شده باشد.
طبق نظریه کولموگوروف، دنباله‌های طولانی با توصیف کوتاه، تصادفی نیستند. یک نتیجه‌گیری اساسی از کار کولموگوروف این بود که میزان تصادفی بودن، بستگی کمی به زبان ریاضی به کار رفته دارد. به عبارت دیگر، در هر زبانی که برای تعریف استفاده شود، اغلب دنباله‌ها «تصادفی» هستند. یعنی به توصیفی، حداقل به بزرگی خود دنباله نیاز دارند. (این مطلب را با یک مثال ساده نیز می‌توان نشان داد. چند عدد شامل n رقم دودویی وجود دارد؟ .
چند عدد دودویی m رقمی مختلف (m < n) توسط یک برنامه قابل تولید است؟ . منظور از تولید عدد توسط برنامه یعنی این که عدد تصادفی نباشد و طبق یک الگوریتم، قابل تولید باشد. حال توجه کنید که اگر m اختلاف کمی هم با n داشته باشد، یعنی مثلاً 10 – n = m ، باز هم تنها یک هزارم خواهد بود. یعنی 9/99 درصد تمام اعداد به طول n، به بیش از 10 – n رقم دودویی برای توصیف نیاز دارند.)
لوین مساله یافتن برنامه ای برای توصیف رشته‌های طولانی را مورد توجه قرار داد و آن را بسیار پیچیده یافت. او در این باره می‌گوید:
«این مساله به همان پیچیدگی مساله یافتن برنامه‌ای سریع و کوتاه برای تولید یک رشته مفروض است. من این ایده به نظرم رسید که آن را به مساله کاشیکاری (پر کردن یک فضا با کاشیهایی در ابعاد مختلف) کاهش دهم اما موفق نشدم. ولی توانستم عمومیت مسائلی نظیر ارضاء‌پذیری، نگاشت گراف و پوشش مجموعه ها را اثبات کنم.»
لوین که در انزوای آن روزهای شوروی از بقیه دنیا بیخبر مانده بود، نمی‌دانست که کوک و کارپ در آمریکا، «عمومیت» این گونه مسائل را نشان داده و انها را مسائل NP کامل نام نهاده‌اند.
«مقالات کوک و کارپ، سالها در شوروی ناشناخته بودند زیرا مجلاتی که این مقالات در آنها چاپ شده بود توسط هیچیک از کتابخانه ها یا موسسات علمی شوروی دریافت نمی‌شد. از سوی دیگر، محدودیت سفر و تبدیل ارز نیز مانع از انجام این کارها از مجراهای خصوصی بود. بعدها، من واقعاً از کارهای کارپ شگفت‌زده شدم زیرا اصلاً انتظار نداشتم اینهمه مساله جالب،‌NP کامل باشند.»
در مقایسه با عکس‌العمل دانشمندان آمریکا به کارهای کوک، عکس‌العملی که در شوروی نسبت به مقاله لوین به عمل آمد، مثبت ولی محدود بود.
«بعضیها به موضوع علاقه‌مند شدند. من دقیقاً نمی‌دانستم که این یک علاقه‌مندی جدی است یا عکس‌العملی احساسی است نسبت به مشکلات سیاسی من: مردم گاهی وقتها بیش از آنچه من استحقاق داشتم رعایت من را می‌کردند. کارهای من در زمان انتشار، سر و صدایی بر نیانگیخت ولی بعد در دهه 1970، مردم شوروی پس از آگاه شدن از کارهای کوک و کارپ، بسیار هیجان زده شدند.»


#@^