P vs NP Roadmap

О проектеOverviewПро проєкт

P против NP — одна из главных нерешённых задач информатики и математики. Упрощённо: правда ли, что любую задачу, решение которой легко проверить, так же легко и найти. За её решение назначен приз в миллион долларов.

Этот проект — попытка систематизировать подходы к проблеме: что про неё известно, какие пути к решению пробовали, где проходит граница изученного.

Чисто исследовательская работа, без прикладного результата. Тут ценна сама постановка вопроса и масштаб задачи, к которой не подступиться нахрапом.

P versus NP is one of the central unsolved problems of computer science and mathematics. Simplified: is it true that any problem whose solution is easy to verify is just as easy to find. A million-dollar prize is set for its solution.

This project is an attempt to systematize approaches to the problem: what's known about it, which paths to a solution have been tried, where the frontier of the studied lies.

Pure research work, with no applied result. What's valuable here is the framing of the question itself and the scale of a problem you can't take by storm.

P проти NP — одна з головних нерозв'язаних задач інформатики й математики. За її розв'язання призначено приз у мільйон доларів.

Цей проєкт — спроба систематизувати підходи до проблеми та межу вивченого.

Суто дослідницька робота — цінна сама постановка питання.

ОсобенностиFeaturesОсобливості

• Систематизация подходов к проблеме P vs NP
• Карта того, что про проблему известно
• Граница изученного в теории сложности
• Чисто исследовательская работа
• Systematizing approaches to the P vs NP problem
• A map of what's known about the problem
• The frontier of the studied in complexity theory
• Pure research work
• Систематизація підходів до проблеми P vs NP
• Карта того, що про проблему відомо
• Межа вивченого в теорії складності
• Суто дослідницька робота