Доведення неможливості
З Вікіпедії, безкоштовно encyclopedia
Доведення неможливості, відоме також як доведення від супротивного, доведення теореми неможливості, або негативний результат — це доведення, яке показує, що конкретна задача не може бути розв'язана, або розв'язання відсутнє взагалі. Часто доведення неможливості потребує багато роботи і часу для того, щоб знайти розв'язок. Щоб довести щось неможливе, необхідно розвинути теорію, і це, зазвичай, набагато складніше, аніж розв'язати протилежне завдання.[1] Теореми неможливості у більшості випадків виражені як універсальні судження в логіці (див. квантор загальності).
Ця стаття містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. |
Одним з найвідоміших є доведення Фердинанда фон Ліндеманна 1882 року, який показав, що стародавня задача про квадратуру круга не може бути розв'язана, тому що число π є трансцендентним (не алгебраїчним) і тільки підмножина алгебраїчних чисел може бути побудована за допомогою циркуля й лінійки. Для двох інших класичних задач — трисекції кута і подвоєння куба, неможливість побудови була доведена у дев'ятнадцятому столітті.
Задачею, що виникла в XVI столітті, було створення загальної формули за допомогою радикалів, що виражають розв'язок будь-яких поліноміальних рівнянь ступеня k, де k ≥ 5. У 1820-х роках, теорема Абеля-Руффіні показала, що це неможливо, з використанням таких понять, як розв'язні групи з теорії Галуа, нового розділу абстрактної алгебри.
Серед найважливіших доведень неможливості у 20-му столітті були задачі алгоритмічної нерозв'язності, які показали, що існують задачі, які неможливо розв'язати взагалі за допомогою будь-якого алгоритму. Найвідомішою є проблема зупинки.
У теорій складності обчислень такі методи, як релятивізація (див. Пророча машина), дають «слабкі» доведення неможливості, за винятком деяких технік доведень. Інші методи, такі як доведення повноти класу обчислювальної складності, свідчать про складність проблем. З цього видно, що їх так само важко розв'язати, як інші відомі проблеми, які виявилися незмінними.