بخشی از مقاله
چکیده
به دست آوردن یک جواب نامنفی برای یک معادله دیوفانتی خطی، در حالت کلی، یک مساله −NPکامل است. در این مقاله نشان می دهیم که اگر همه مولفه های بردار ضرایب معادله دارای یک علامت نباشند، آنگاه می توان یک - و حتی بینهایت - جواب نامنفی را برای معادله در یک زمان چند جمله ای به دست آورد. بنابراین، در این حالت مساله فوق جزء رده مسایل ، Pمسایل به طور چند جمله ای حل پذیر، است. الگوریتم ارایه شده در اینمقاله برای تولید جواب های نامنفی یک معادله دیوفانتی، یک الگوریتم ساده و سریع است. برای تولید جواب های نامنفی یک معادله دیوفانتی شدنی، ابتدا نوع خاصی از جواب های صحیح نامنفی را برای معادله همگن متناظر به دست می آوریم. سپس یک ترکیب خطی صحیح نامنفی مناسب از آنها را به یک جواب خاص معادله دیوفانتی اضافه می کنیم تا یک بردار صحیحنامنفی، که در واقع یک جواب نامنفی برای معادله دیوفانتی است، به دست آید.
۱. مقدمه
یک معادله دیوفانتی خطی با متغیرهای نامنفی در نظر بگیرید:که در آن ..., an - T ∈ Zn ,۱a = - a و .b ∈ Z این مساله اغلب به عنوان یک زیر مساله در طراحی هاICبرای پردازش سیگنال های ویدیویی بروز می کند.هم چنین، مسایلی وجود دارند که از نوع مساله - ۱.۱ - یا تعمیمی از آن هستند،مانند مساله فروبنیوس که اخیراً توسط کارنیوجولس، یوربانیاک، وایسمنتل و وُلسی ]۱[ در نظر گرفته شده است. نمونه های کلی تر مساله - ۱.۱ - که مربوط به پردازش سیگنال های ویدیویی می شوند برای حل با روش انشعاب و تحدید
واﮊگان کلیدی:معادلات. دیوفانتی، جواب های صحیح، جواب های نامنفی .
در برنامه ریزی صحیح، به واسطه طبیعت داده ها، خیلی سخت هستند.یک روش طبیعی برای حل مساله - ۱.۱ - عبارت است از تبدیل - ۱.۱ - به یک مساله برنامه ریزی خطی صحیح و حل آن با روش های برنامه ریزی صحیح.یک مساله برنامه ریزی خطی صحیح با قیدهای - ۱.۱ - و یک تابع هدف، مثلاً + · · · + xn ۲+ x ۱x، در نظر بگیرید که هدف آن کمینه سازی است:در اینجا، e یک بردار nبعدی با مولفه های یک است. توجه داریم که هر جواب بهینه، در صورت وجود، برای - ۱.۲ - یک جواب شدنی برای - ۱.۱ - است. مساله برنامه ریزی صحیح - ۱.۲ - را می توان با هر یک از الگوریتم های برنامه ریزی صحیح، مانند الگوریتم صفحه برشی یا الگوریتم انشعاب و تحدید]۲،۳،۴[، حل کرد.
روش صفحه برشی به دلیل خطاهای گرد کردن عموماً یک روش همگرا نیست و بندرت مورد استفاده قرار می گیرد. بنابراین برای حل مساله - ۱.۲ - از روش انشعاب و تحدید استفاده می شود. در حل یک مساله شدنی بودن، مانند مساله - ۱.۱ - ، با روش انشعاب و تحدید، دو مشکل اساسی وجود دارد. اولاً، ممکن است درخت جستجو خیلی بزرگ شود. ثانیاً، ممکن است خطاهای گرد کردن رخ دهند. به علاوه، اندازه درخت جستجو نسبت به تابع هدف مورد استفاده حساس است و نیز زمان حل مساله بستگی به تابع هدف انتخاب شده دارد. بنابراین، یک مشکل دیگر انتخاب بهترین تابع هدف است.
هم چنین، یک تابع هدف مفهومی به مساله القا می کند که طبیعی نیست. برای حل مساله - ۱.۱ - از هیچ تابع هدفی استفاده نمی کنیم چون مساله صرفاً یک مساله شدنی بودن است؛ به محض این که یا یک بردار شدنی بیابیم یا نشان دهیم که هیچ چنین برداری وجود ندارد مساله حل شده است و نیازی به تابع هدف نیست.برای رفع نواقص فوق الگوریتمی ارایه می کنیم که الف - فقط با اعداد صحیح کار می کند و بنابراین مشکلات گرد کردن را ندارد؛
ب - چون این الگوریتم فقط برای مساله شدنی بودن طراحی شده است، پس نیازی به تعریف یک تابع هدف نیست.
۲. نتایج اصلی
معادله - ۲.۱ -
را در نظر بگیرید، که در آن ..., an - T ∈ Zn ,۱a = - a و .b ∈ Z در حالت کلی مساله - ۲.۱ - یک مساله −NP کامل است ]۴.[ به طور »سازنده« نشان می دهیم اگر همه مولفه های بردار ضرایب a دارای علامت یکسان نباشند، آنگاه می توان یک - و حتی بینهایت - جواب را برای - ۲.۱ - در یک زمان چند جمله ای به دست آورد. بنابراین، در این حالت مساله - ۲.۱ - جزء رده مسایل P، مسایل به طور چند جمله ای حل پذیر، است. الگوریتم ارایه شده در این بخش برای حل - ۲.۱ - یک الگوریتم ساده و سریع است و کار اصلی در آن یافتن بزرگترین مقسوم علیه مشترک دو عدد صحیح می باشد. برای حل مساله - ۲.۱ - ابتدا نوع خاصی از جواب های صحیح نامنفی را برای معادله همگن متناظر به دست می آوریم.
سپس، یک ترکیب خطی صحیح نامنفی مناسب از آنها را به یک جواب خاص معادله دیوفانتی اضافه می کنیم تا یک بردار صحیح نامنفی، که درواقع یک جواب نامنفی برای معادله دیوفانتی است، به دست آید. توجه داریم که مساله را، که در آن ∈ Zn ،uمی توان با جایگزینی y = u − x به صورت نوشت که از نوع - ۲.۱ - می باشد. بنابراین الگوریتم ارایه شده در این بخش را می توان برای حل مساله - ۲.۲ - نیز به کار برد. به هر حال، با یک تغییر جزیی در الگوریتم می توان مساله - ۲.۲ - را مستقیماً حل کرد و نیازی به تبدیل آن به صورت - ۲.۱ - نمی باشد.مساله همگن متناظر با - ۲.۱ - را در نظر بگیرید:
به علاوه، J+ ∩ J = ϕ و ..., n} ,۲ ,۱.J+ ∪ J = { توجه داریم که مساله - ۲.۴ - همواره شدنی است. در ادامه، نوع خاصی از جواب های - ۲.۴ - را تولید می کنیم و سپس از آنها برای به دست آوردن یک جواب برای - ۲.۱ - استفاده می کنیم. جواب هایی که برای - ۲.۴ - تولید می کنیم فقط دو مولفه مثبت دارند و بقیه مولفه های آنها صفر می باشند. به علاوه، این جواب ها اولیه هستند. منظور از یک جواب اولیه جوابی است که اولاً غیر بدیهی است و ثانیاً هیچ جواب غیربدیهی کوچکتر از آن وجود ندارد.به ازای هر ∈ J+ ۱j و هر ∈ J ۲j قرار دهید. - ۲.۵ -
