به دست آوردن یک جواب نامنفی برای یک معادله دیوفانتی خطی، دهیم − کامل است. در این مقاله نشان می NP در حالت کلی، یک مساله های بردار ضرایب معادله دارای یک علامت نباشند، آنگاه که اگر همه مولفه توان یک (و حتی بینهایت) جواب نامنفی را برای معادله در یک زمان چند می ای به دست آورد. بنابراین، در این حالت مساله فوق جزء رده مسایل جمله پذیر، است. الگوریتم ارایه شده در این ای حل ، مسایل به طور چند جمله P های نامنفی یک معادله دیوفانتی، یک الگوریتم ساده مقاله برای تولید جواب های نامنفی یک معادله دیوفانتی شدنی، و سریع است. برای تولید جواب های صحیح نامنفی را برای معادله همگن متناظر ابتدا نوع خاصی از جواب آوریم. سپس یک ترکیب خطی صحیح نامنفی مناسب از آنها به دست می کنیم تا یک بردار صحیح را به یک جواب خاص معادله دیوفانتی اضافه می نامنفی، که در واقع یک جواب نامنفی برای معادله دیوفانتی است، به دست آید.
