در نظریه پیچیدگی رایانشی، قضیه کوک و لوین، که گاه قضیه کوک نیز خوانده می شود، نشان می دهد که مسئله صدق پذیری دودویی مسئله ای ان پی کامل است: الگوریتم نمی شناسیم که در زمانی کوتاه مسئله صدق پذیری را حل کند. این مسئله نخستین مسئله ای است که ان پی کامل بودنش نشان داده شده است. می توان این مسئله را به بسیاری دیگر از مسئله ها کاست و ان پی کامل بودنشان را نشان داد. این دسته از مسئله ها با نام دسته یا کلاس ان پی شناخته می شوند. از همین روی قضیهٔ کوک و لوین یکی از مهم ترین قضیه ها در زمینهٔ پیچیدگی رایانشی است. برآیهٔ (نتیچه ی) مهم این قضیه چنین است: اگر الگوریتمی با ییچیدگی زمانی چندجمله ای یکی از مسئله های دستهٔ ان پی کامل حل کند، همهٔ مسئله های دیگر را نیز می توان با پیچیدگی زمانی چندجمله ای حل نمود. این برآیه مسئله ای را به نام برابری پی و ان پی پیش می کشد که یکی از مهم ترین پرسشِ های بی پاسخ در دانش رایانه است. این نظریه به پاس داشت استیون کوک و لنوید لوین نام گذاری شده است.
پژوهندگان شوروی و آمریکا هم زمان نظریهٔ ان پی کامل را در پایان دههٔ ۱۹۶۰ و آغاز دههٔ ۱۹۷۰ پدیدآوردند. در آمریکا در سال ۱۹۷۱، استیون کوک مقالهٔ «پیچیدگی قضیهٔ آوین رویه ها» را در کنفرانس «انجمن نظریهٔ رایانش» چاپ کرد. به دنبالِ آن، ریچارد کارپ در سال ۱۹۷۲ مقالهٔ «کاهش میانِ مسئله های ترکیبی" را چاپ نمود. او به کمک نظریهٔ کوک فهرستی از ۲۱ مسئله ان پی-کامل کارپ را شناسایی کرد و نشان داد که چگونه در زمانی کوتاه می توان مسئله صدق پذیری دودویی را به این مسئله ها کاست. از همین روی، ریچارد کارپ و کوک جایزه تورینگ دریافت کردند. سپس، تیودور پی بیکر، جان گیل و روبرت ام سولووی در سال ۱۹۷۵ نشان دادند که حل مسئله های ان پی در ماشین سروش نیازمند زمانی نمایی است.
در شوروی در سالِ ۱۹۶۹، ام دختیار نتیجه ای همانند نتیجهٔ بیکر، گیل و سولووی را به چاپ رسانید. سپس در سال ۱۹۷۳، مقالهٔ لوین «مسئله همگانی جستجو» به چاپ رسید. گرچه پیش از این مقاله در گفت وگوها یاد شده بود و در چند سال پیش برای چاپ فرستاده شده بود. دگرسانیِ رویکردِ لوین با رویکردِ کوک و کارپ در این است که لوین جست وجوهایی که راه حل را می جویند بررسی می کرد ولی کوک و کارپ بودنِ چنین راه حل هایی را بررسی می کردند. لوین ۶ مسئله جستجوی مسئله های همگانی (ان پی کامل) را شناساند و نشان داد که اگر الگوریتم جست وجویی با پیچیدگی زمانی چندجمله ای باشد که یکی از این مسئله ها را حل کند، می توان دیگر مسئله ها نیز با پیچیدگی زمانی چندجمله ای حل نمود.
یک مسئله تصمیم ان پی خوانده می شود اگر بتوان آن را به کمک یک الگوریتم غیرقطعی در زمان چندجمله ای حل کرد.
پژوهندگان شوروی و آمریکا هم زمان نظریهٔ ان پی کامل را در پایان دههٔ ۱۹۶۰ و آغاز دههٔ ۱۹۷۰ پدیدآوردند. در آمریکا در سال ۱۹۷۱، استیون کوک مقالهٔ «پیچیدگی قضیهٔ آوین رویه ها» را در کنفرانس «انجمن نظریهٔ رایانش» چاپ کرد. به دنبالِ آن، ریچارد کارپ در سال ۱۹۷۲ مقالهٔ «کاهش میانِ مسئله های ترکیبی" را چاپ نمود. او به کمک نظریهٔ کوک فهرستی از ۲۱ مسئله ان پی-کامل کارپ را شناسایی کرد و نشان داد که چگونه در زمانی کوتاه می توان مسئله صدق پذیری دودویی را به این مسئله ها کاست. از همین روی، ریچارد کارپ و کوک جایزه تورینگ دریافت کردند. سپس، تیودور پی بیکر، جان گیل و روبرت ام سولووی در سال ۱۹۷۵ نشان دادند که حل مسئله های ان پی در ماشین سروش نیازمند زمانی نمایی است.
در شوروی در سالِ ۱۹۶۹، ام دختیار نتیجه ای همانند نتیجهٔ بیکر، گیل و سولووی را به چاپ رسانید. سپس در سال ۱۹۷۳، مقالهٔ لوین «مسئله همگانی جستجو» به چاپ رسید. گرچه پیش از این مقاله در گفت وگوها یاد شده بود و در چند سال پیش برای چاپ فرستاده شده بود. دگرسانیِ رویکردِ لوین با رویکردِ کوک و کارپ در این است که لوین جست وجوهایی که راه حل را می جویند بررسی می کرد ولی کوک و کارپ بودنِ چنین راه حل هایی را بررسی می کردند. لوین ۶ مسئله جستجوی مسئله های همگانی (ان پی کامل) را شناساند و نشان داد که اگر الگوریتم جست وجویی با پیچیدگی زمانی چندجمله ای باشد که یکی از این مسئله ها را حل کند، می توان دیگر مسئله ها نیز با پیچیدگی زمانی چندجمله ای حل نمود.
یک مسئله تصمیم ان پی خوانده می شود اگر بتوان آن را به کمک یک الگوریتم غیرقطعی در زمان چندجمله ای حل کرد.
wiki: قضیه کوک لوین