Самый простой способ - доказать, что существует решение за полиномиальное время в классе NP-complete. Это проблемы, которые есть в NP и сводятся к одной из известных проблем np. Это означает, что вы могли бы дать более быстрый алгоритм для доказательства исходной проблемы , поставленной Стивеном Куком или многими другими, которые также были доказаны как NP-Complete. См. оригинальную бумагу Ричарда Карпа и этой книги для более интересных проблем. Было показано, что если вы решите одну из этих проблем, весь класс сложности рухнет. редактировать: я должен добавить, что я разговаривал с моим другом, который изучает квантовые вычисления. Хотя я понятия не имел, что это значит, он сказал, что это определенное доказательство / эксперимент? в квантовом мире может сделать весь класс сложности, я имею в виду все это, спорный. Если кто-то здесь знает больше об этом, пожалуйста, ответьте.
Были также многочисленные попытки решения проблемы без предоставления формального алгоритма. Вы можете попытаться посчитать набор. Есть доказательство Роберта / Сеймора. Люди также пытались решить эту проблему, используя проверенное и проверенное доказательство диагонализации (также использовалось, чтобы показать, что есть проблемы, которые вы никогда не сможете решить). Разборов также показал, что если существуют определенные односторонние функции, то любое доказательство не может дать решение. Это означает, что для решения этого вопроса потребуются новые методы.
Прошло 38 лет с момента публикации оригинальной статьи, и до сих пор нет никаких признаков доказательства. Не только это, но и множество проблем, которые математики ставили до того, как появилось понятие классов сложности, было доказано как NP. Поэтому многие математики и ученые-компьютерщики считают, что некоторые проблемы настолько фундаментальны, что для их решения может потребоваться новый вид математики. Вы должны помнить, что лучшие умы, которые может предложить человеческая раса, решили эту проблему без какого-либо успеха. Я думаю, что должно пройти не менее десятилетий, прежде чем кто-то взломает головоломку. Но даже если существует решение за полиномиальное время, константы или показатель степени могут быть настолько большими, что это будет бесполезно в наших задачах.
Существует отличный опрос, который должен ответить на большинство ваших вопросов: http://www.scottaaronson.com/papers/pnp.pdf.