Крипто-форум crprogram.16mb.com

Програмування, Delphi, криптографія, криптоаналіз, шифри, вихідні коди, вирішення задач, приклади програм

Часовий пояс: UTC десь + 2 години




Розпочати нову тему Відповісти  [ 9 повідомлень ] 
Автор Повідомлення
 Заголовок повідомлення: Гіпотеза: NP не дорівнює P, зрозуміле доведення, російською
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 14
На жаль, буду користуватись російською мовою, так як стаття, надрукована російською мовою, в україномовні журнали не мав змоги відправити, на жаль :( анотація, та назва статті- англійською, сама стаття -російською журнал знаходиться тут: (в співавторстві з паном Ковалем В.В.)стаття з
назвою "NP not equal to P" стаття вийшла в рецензуємому
журналі, російською мовою.
30.10.2013 року вийшов у світ №5/2013 журналу “Eastern European Scientific Journal”.
Посилання на журнал у інтернеті
DOI_10.12851_EESJ201310_2_.pdf с.114

Електронна копія журналу, знаходиться у вільному доступі.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: NP не дорівнює P, зрозуміле доведення, нажаль російською
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 502
Добре, почитаємо, подивимось.

Додам від себе, що доведення рівності класів складності P і NP є однією з Задач тисячоліття (список підготовлений інститутом Клея у 2000 році), за вирішення якої дадуть 1млн. долларів США.
І її так поки що і не довели.

Можливо автор довів - будемо чекати підтвердження науковців.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: NP не дорівнює P, зрозуміле доведення, нажаль російською
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 14
якщо виникнуть питання, залюбки відповім! :)


Повернутися наверх
  
 
 Заголовок повідомлення: Re: NP не дорівнює P, зрозуміле доведення, нажаль російською
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 24
Цитата:
Not Found

The requested URL /mediapool/99/990918/data/DOI_10.12851_EESJ201310_1_.pdf was not found on this server.

Документ не відкривається.
:?:


Повернутися наверх
  
 
 Заголовок повідомлення: Re: NP не дорівнює P, зрозуміле доведення, нажаль російською
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 14
Тоді зайдіть по посиланнях: www.auris-verlag.de за посиланням Journal и далі Eastern European Scientific Journal October 2013


Повернутися наверх
  
 
 Заголовок повідомлення: Re: Гіпотеза: NP не дорівнює P, зрозуміле доведення, російсь
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 282
Виправив посилання, документ відкривається.

Я не вчений у галузі теоритичної математики, та все таки бачу у вашій статті деякі проблеми.

  • Ви намагаєтесь довести нерівність, в той час як практичну цінність становить саме рівність, тобто якщо NP=P - сучасна криптографія просто буде неспроможна захистити секрети.
  • Ви доводите методом індукції - таким методом ви можете довести, що для декількох задач дійсно рівність не виконується, але це не буде означати що для інших задач вона не виконується. (задача про чорних та білих воронів - якщо ви постійно бачите тільки чорних, це ще не значить що не може бути білих).
  • Основою вашого доведення є рішення конкретної задачі , що не говорить абсолютно нічого про такі актуальні проблеми сучасної криптографії як швидка факторизація натуральних чисел і т.д. (я не перевіряв ваші доведення - можливо вони і вірні, навіть якщо воно і вірне - це ще не означає доведення рівності для незліченного класу задач)
  • Також почитав інші наукові статті того журналу і склалось суб'єктивне враження у низькому науковому рівні деяких статей. Деякі з тих статей більше на недолугі реферати студентів схожі - а отже це наштовхує на думку що статті редактори не перевіряють, або перевіряють поверхнево. ( а чи знають німці російську мову? ;) )

Загалом - те що ви, якщо навіть і, довели задачу для певної конкретної задачі ніяк не доводить рівність/не рівність.

Ще особисте побажання - у вашій статті попри те що є купа малюнків відсутня наочність.
Вам би варто було намалювати графи, якщо оперуєте їх частинами - показувати ті частини і т.д.
Купа малюнків зі стрілками та розфарбованими областями це чудово, але тільки для стороннього спостерігача, який не буде розбирати вашу статтю.

Ось приклад скажімо схеми AES
images/crprimg/t21-1.png
навіть люди які не знають криптографії наочно бачать "що? як? де?"
Якщо цю схему зобразити тільки блоками з підписами - наочність втрачається.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: Гіпотеза: NP не дорівнює P, зрозуміле доведення, російсь
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 14
нерівність NP та P має більшу цінність ніж їх рівність, тому, шо сучасна банківська система базується на криптографії:)
і рівність NP та P буде означати великі збитки для банківської системи.
індукція при її вірному застосуванні має право на життя :)
такі питання, як швидка факторизація, та інші питання, не є темою цього дослідження, але можливо, що цей метод дасть змогу на ці питання відповісти :)
так, Ви вірно підмітили, що математика на цьому не вмирає, і залишається ще купа незличена питань, навіть у області NP-повних задач.
вважаю, що деякі німці, розуміють не тільки російську, але й українську мову :)
велике спасибі за питання:)
з повагою Білан І.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: Гіпотеза: NP не дорівнює P, зрозуміле доведення, російсь
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 282
mathbilan писал(а):
нерівність NP та P має більшу цінність ніж їх рівність, тому, шо сучасна банківська система базується на криптографії:)
і рівність NP та P буде означати великі збитки для банківської системи.

Звісно так, і ваше доведення це лише невеликий крок у тому напрямку.

Але, у криптографії ви ніколи не будете впевнені що "завтра" не винайдуть новий вид криптоаналізу і не зламають той чи інший шифр. Імовірність мала, але вона є.

Розглянемо конкретний приклад.

Шифр простої підстановки.

Для його криптоаналізу грубою силою необхідно перебрати (33!-1) варіантів перестановки літер.
Що, навіть зараз, це не здійсненна задача.

При доведенні стійскості таких шифрів новачки, як правило, починають розказувати що число 10^36 надзвичайно велике, починають порівнювати його з кількістю атомів у Всесвіті і т.д.

У той час такі шифри ламаються частотним аналізом, а при KPA його стійкість падає катастрофічно.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: Гіпотеза: NP не дорівнює P, зрозуміле доведення, російсь
СообщениеДодано: 09 гру 2014, 20:48 
Не в мережі

Повідомлень: 14
Звісно, це так!
з повагою Білан І.


Повернутися наверх
  
 
Показати повідомлення за:  Сортувати по:  
Розпочати нову тему Відповісти  [ 9 повідомлень ] 

Часовий пояс: UTC десь + 2 години



cron
Роwеrеd bу рhрВB® аnd Hostinger web hosting