Не хвилюйтеся, я не збираюся просити вас вирішити цю задачу. Якщо ви це зробите, то можете отримати мільйон доларів. але зараз це питання ставить в тупик найсильніших математиків світу. Цілком може бути, що це найскладніша, сама дратує, сама не піддається математична задача з усіх, що існували коли-небудь. Це проблема P / NP, і як не дивно, вона полягає в тому, чи існують насправді складні математичні завдання.
Якщо поставити питання таким чином, то все елементарно. Якщо немає, дев'яносто дев'ять відсотків людства страждає від колективного помилки. Більшість математиків згодні з існуванням таких завдань, вони не вірять в існування такої речі як безкоштовний обід. Але саме зараз вони не можуть довести свою правоту.
Проблема виникла в інформатиці. Ми зазвичай вважаємо обчислення інструментом для розуміння математики, але тут математика постає інструментом для розуміння обчислень. Комп'ютери надають фантастичну допомогу математикам. Іноді вони в одну мить дають відповідь, тоді як для його отримання за допомогою олівця і паперу будуть потрібні об'єднані зусилля всіх людей на планеті протягом мільйона років. Але іноді навіть найшвидший суперкомп'ютер допоможе не більше, ніж рахунки дитини.
P / NP - математична задача про те, як комп'ютер вирішує математичні задачі. Комп'ютери гарні в деяких завданнях, проте вони не приносять користі в інших. Проблема полягає не в тому, щоб вирішити, що є що. Потрібно довести, що дійсно є різниця.
Для користувачів має значення не тільки результат роботи алгоритму, а й як швидко машина отримує цей результат. Наприклад, існує дуже простий алгоритм для написання бестселера. Згенерувати всі можливі книги з 100000 слів, оцінити їх читабельність, і вибрати кращу з них. Однак вийде так багато варіантів, що цей алгоритм невдалий, яким би дорогим не був ваш комп'ютер.
Алгоритми, які працюють швидко, називаються алгоритмами класу P. Ця перша буква слова "polynomial '' (поліноміальний) - так, тепер це починає звучати як математика - яке описує, як швидко зростає час обчислень в залежності від збільшення обсягу вихідних даних. Всі інші алгоритми - Ні-P, вони працюють занадто повільно, щоб вважатися корисними, за кількома почесними винятками. Алгоритм "написати всі можливі книги '' приблизно такий же, як і-P, як ви можете бачити. Так як довжина книги збільшується, час роботи зростає навіть швидше, ніж поголів'я безсмертних кроликів, подвоюється кожні кілька місяців, поки ці кролики не утворюють сферу, що оточує Землю і розширюється зі швидкістю більшою, ніж швидкість світла.
"Р або НЕ-Р, ось в чому питання '', - майже так сказав Гамлет. Як правило, можна з'ясувати ефективність будь-якого конкретного алгоритму. Однак все йде шкереберть, коли ми думаємо не про алгоритм, а про завдання, яке він вирішує. Чи існує більш швидкий алгоритм вирішення тієї ж завдання? Якщо так, то завдання може бути легко вирішена, ви просто використовуєте не той метод.
Проблема належить класу P, якщо існує ефективний алгоритм її вирішення, і Класу не-P, якщо немає. "Ось в чому питання '', як сказав Гамлет все в тій же промові. Що можна зробити? Ви не можете випробувати всі можливі алгоритми по черзі - це як написати всі можливі книги, але тепер без обмеження за кількістю слів. Якщо ви знайшли ефективний алгоритм, то завдання, безумовно, класу P. Але якщо ваш алгоритм є неефективним ... можливо, існує інший алгоритм, кращий, який ви ще не виявили.
Незважаючи на це, ми безсумнівно можемо довести, що деякі завдання належать Класу не-P. "Напишіть всі можливі книги '' - приклад такого завдання: якою б алгоритм ви ні використовували, він повинен давати відповідь, а це займе нескінченне час. Клас NP виключає такі дурні завдання, як ця. Він виділяє потенційно складні завдання, які мають короткий і точний відповідь. Букви NP означають "nondeterministic polynomial '' (" невизначений поліноміальний ''), і N-слово означає саме те, про що ви здогадалися. Будь-яке припущення можна перевірити дуже швидко, але це не допоможе вам вирішити задачу, якщо вам часом не пощастить.
Мій алгоритм написання бестселера не є NP. Обсяг отриманих книг гігантський, і щоб переконатися в правильності результату, ви повинні прочитати все, щоб переглянути, що нічого не було упущено. Відчутно важкі завдання - це завдання, відповідь в яких можна легко перевірити, якщо ви його знаєте, проте важко знайти цю відповідь.
Це NP-задачі, які не є P-завданнями. І ось питання на мільйон доларів, P / NP завдання:
NP відрізняється від P?
Чи існують завдання, в яких легко перевірити здогад, але практично неможливо знайти правильну відповідь? Більшість математиків очікують, що відповідь на це питання буде "так" ", але є і сумніви. Може бути, є якийсь хитрий спосіб знайти правильний здогад дуже швидко, але ми занадто дурні, щоб виявити його.
Є сотні проблем, які, як думають математики, повинні бути NP, але не P. Завдання комівояжера є однією з них: який найкоротший шлях, що проходить через всі міста зі списку? (Майте на увазі, ми навіть не впевнені, що це NP, яка дійсно кидає виклик.) У будь-якому разі не відомо ефективного алгоритму вирішення цього завдання, і ми не очікуємо, що він знайдеться, але ми не можемо довести, що його не існує . Таким чином, незважаючи на обтяженість великими грошима, P / NP-проблема залишається відкритою. Не здивуюся, якщо вона не буде вирішена ще сто років.
2 Піфагор-9:
Цікава тема-стара як мір.Человеческое свідомість, та й не тільки людське, в повсякденної реальності змушене йти своїм путем.Где дрібними кроками, де гиганскими кроками рухаючи еволюцію в тривимірному просторі взаємодіючих состояній.Виход один-СТРАТЕГІЯ і ТАКТІКА.Налічіе системи проектування гранично оптимальних систем (СППОС), незалежно від обсягу поєднуваних елементів-дозволить, на попередньому етапі, позбутися від колллосального кількості непотрібних станів, за відомим алгоритмом, з мінімізованої помилкою, ан логічно того як помиляється сама Прірода.Фактор часу, в дінамікке подій, дуже важливий і не треба зациклюватися на статичному стані об'єкта, яка не мможет осягнути неосяжне в каруселі життя.
3 касембай амір:
алгоритм p вирішує складні завдання як і ір немає різниці