Какво представлява проблемът на хилядолетието?

Въпрос: Какво представлява проблемът на хилядолетието?

О: Проблемът на хилядолетието е един от най-важните и предизвикателни математически проблеми на този век, който разглежда въпроса дали всяка задача, която е лесна за проверка от компютрите, е и лесна за решаване.

В: Как можем да класифицираме математическите проблеми?

О: Математическите проблеми могат да бъдат класифицирани като P или NP проблеми въз основа на това дали са решими за крайно полиномиално време.

В: Каква е разликата между P и NP задачите?

О: P проблемите са сравнително бързи и "лесни" за решаване от компютрите, докато NP проблемите са бързи и "лесни" за проверка от компютрите, но не е задължително да са лесни за решаване.

Въпрос: Кой е въвел проблема P срещу NP?

О: Стивън Кук въвежда проблема P срещу NP през 1971 г. в статията си "Сложността на процедурите за доказване на теореми".

В: Защо проблемът P versus NP е важен?

О: Проблемът P versus NP се счита за най-важния отворен проблем в информатиката и е един от седемте проблема, наградени с наградата на хилядолетието, с награда от 1 000 000 долара за решение, което предизвиква публикувано признание от Института Клей и вероятно такова(и), което(ито) променя(т) цялата математика.

Въпрос: Възможно ли е да се реши задача с NP-пълнота за квадратично или линейно време?

О: През 1956 г. Курт Гьодел пише писмо до Джон фон Нойман, в което пита дали определен NP-комплексен проблем може да бъде решен за квадратично или линейно време.

Въпрос: Защо много математици се надяват, че проблемите на хилядолетието са свързани помежду си?

О: Много от проблемите на хилядолетието засягат свързани въпроси и мечтата на много математици е да се създадат обединяващи теории.