Русская Америка - Russian America.
Руссике артисты на Американской сцене
Новости на Русской Америке News События на Русской Америке Events Yellow Pages на Русской Америке Yellow Pages Доска объявлений на Русской Америке Classifieds Russian TV and Video TV/Video Знакомства на Русской Америке Dating Форум на Русской Америке Forum Чат на Русской Америке Chat Фотоальбомы RussianAmerica Photos
Русские в Америке. Русские знакомства, чат, форум.
Russian Chat, russian forum, russian dating.
 Entertainment
Home
  
Анекдоты
  отобранные
Истории
Загадки
Афоризмы
  
  
Картинки
  Эро-юмор
  Этикетки
  
Рассылки
  Гороскоп по почте
  TV-программа
  Анекдоты
  ... еще ...

  
Открытки
  Поздравь друга
  
  
Игры
  Классические
  Спортивные
  Игровые автоматы
  Забавные

Игры на
компьютере


  
Читальный зал
  Стихи
  Проза
  Кулинария

Едем в Америку!
  Иммиграция
  Визы
  Советы

Обзоры Exler.ru
  Web Обзоры
  Обзоры фильмов
  Рассказы
  ЭКСпромт:
  Для чайников

Гороскопы

Знакомства
  
Фотоальбомы
  America views
  Personal
  Создай свой альбом
  
Рассылки:
  Новости-почтой
  TV-Программа
  Гороскопы
  Job Offers
  Концерты
  Coupons
  Discounts
  Иммиграция
  Business News
  Анекдоты
Многое другое...
 Другие ресурсы
NEWS CENTRAL
  
Программа TV
Finance News
Мода
Кино
  Новости кино
  Кинообзоры
Спорт
Музыка

  Штаты
Едем в Америку!
  Иммиграция
  Визы
  Советы

Russian America Journal Digest
  
Yellow Pages
Объявления
Чат
Форум
  последнее
Top Rating
  America TOP
  
 
Entertainment HomeАнекдоты

Математик Винай Деолаликар из лабораторий Hewlett-Packard в Пало-Альто, Калифорния уверен, что доказал известное в информатике утверждение "Р не равно NP"
Вопрос "P и NP" относится к скорости, с которой компьютер решает такую задачу, как, например, разложение числа на множители
Аргументация Деолаликара построена на задаче выполнимости булевых формул, которая заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ложь и истина так, чтобы формула стала истинной

Ученый из США утверждает, что решил одну из математических "задач тысячелетия". Математик Винай Деолаликар из лаборатории Hewlett-Packard в Пало-Альто, Калифорния, уверен, что доказал известное в информатике утверждение "Р не равно NP", сообщает The New Scientist.

Это открытие позволит компьютерам решать многие задачи. В случае его подтверждения Деолаликар получит приз в 1 млн долларов от Математического института Клэя, поскольку данная задача - одна из семи проблем, за решение которых обещан такой приз.

Последним, кто решил одну из "задач тысячелетия", оказался российский математик Григорий Перельман. Ученый-эксцентрик из Санкт-Петербурга живет затворником и практически не общается с коллегами. Свое доказательство гипотезы Пуанкаре, над которой около ста лет ломали голову лучшие умы мировой математики, он опубликовал в интернете. Когда же Перельману предложили получить премию в миллион долларов, он отказался и даже не приехал на церемонию награждения за символическим призом.

Вопрос "P и NP" относится к скорости, с которой компьютер решает такую задачу, как, например, разложение числа на множители. Некоторые задачи могут решаться за достаточно короткий период времени, поскольку продолжительность их решения пропорциональна объему введенной информации. Эти задачи включены в класс P.

Если ответ можно проверить быстро, тогда эта задача находится в классе NP. Так что если P=NP, то каждая задача, решение которой можно проверить быстро, соответственно, может быть и решена с высокой скоростью. Этот вывод может иметь весьма серьезные последствия для обеспечения безопасности в интернете, где трудности при разложении на множители очень больших чисел являются основным барьером, который выставляют на пути хакеров.

Но Деолаликар не согласен с этим. Его аргументация построена на задаче выполнимости булевых формул, которая заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ложь и истина так, чтобы формула стала истинной. Эту задачу относят к разряду NP. Деолаликар утверждает, что нет такой программы, которая может с самого начала быстро выполнить такой подсчет, и поэтому этой проблеме нельзя придать статус P.

Таким образом, задачи разрядов P и NP не идентичны, поэтому на способности компьютеров накладываются серьезные ограничения: многие задачи останутся фундаментально сложными без возможности их облегчения. Для некоторых проблем, включая разложение числа на множители, полученный Деолаликаром результат не дает однозначного ответа, могут ли они быть решены быстро. Но значительный массив задач, называемый NP-завершенные, окажется под угрозой. Известным примером является задача про коммивояжера, которому нужно найти кратчайший маршрут через набор городов. Такие задачи имеют быстрое решение, но если P не равно NP, тогда нет такой компьютерной программы, которая может быстро их решить.

Свои соображения Деолаликар представил на всеобщее обозрение в интернете, пишет британская газета The Daily Telegraph.

Чтобы легче понять проблему, Математический институт Клэя приводит такой пример: вы должны разместить 400 студентов в 100 аудиториях. Декан снабдил вас списком, в котором перечислены пары студентов, не подходящих друг другу, и велел сделать так, чтобы ни в одной из аудиторий ни один студент не встретил ни одного другого студента, с которым находится в неприязненных отношениях.

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

Общее количество операций, которые нужно произвести, чтобы оптимально заполнить 100 аудиторий студентами, превышает количество атомов в известной части Вселенной. Таким образом, невозможно построить такой суперкомпьютер, который сможет решить проблему "грубой силой" или простым перебором вариантов - всех комбинаций из 100 аудиторий со студентами.

Но на самом деле одна из выдающихся проблем информатики в том, чтобы определить, есть ли такие вопросы, ответы на которые можно быстро проверить, но которые требуют невозможно долгого времени на решение каким-либо непосредственным способом.

Профессор Массачусетского института технологии Скотт Ааронсон настроен скептически: он взялся заплатить Деолаликару 200 000 долларов, если Институт Клэя утвердит его открытие. Профессор Ааронсон написал, что еле наскребет эту сумму, но пояснил: "Если проблема неравенства P и NP действительно решена, моя жизнь претерпит такой крутой поворот, что выплата двухсот тысяч долларов будет лишь самым незначительным событием в ней".

  1. Белорусской оппозиции понравилась резкая отповедь Медведева в адрес Лукашенко: ее донесут до Европы...

  2. Прямые переговоры с палестинцами начнутся в ближайшие дни, пообещал министр обороны Израиля...

  3. Инопресса назвала Ходорковского вторым по влиятельности заключенным в мире...

  4. Воздушное пространство Абхазии Россия защитит от нарушителей ракетами С-300: уничтожат всех...


  5. США, Россия и Канада остались довольны общей победой над выдуманными "воздушными террористами"...

  6. У итальянки в руке лопнул тюбик китайского клея: пальцы не могут разъединить уже неделю...

  7. На Украине тоже готовятся переименовать милицию. Но слово "полиция" не подходит...

  8. США советуют отказаться от тактики "мягкой силы" в борьбе за сферы влияния: Россия понимает лишь грубость...

  9. Американский "бешеный стюард", сбежавший из самолета, стал звездой - у него тысячи фанатов...

  10. Мозг работает по принципу интернета, выяснили ученые...

  11. В Киргизии арестован бывший премьер-министр...

  12. Телескоп Hubble сфотографировал "галактику-колесо" в 320 млн световых лет от Земли...

  13. "Шпион" Сутягин рассказал, как его тайно меняли на пойманных в США российских агентов...

  14. Ученые нашли связь между жарой в России и потопом в Пакистане...

  15. США выделяют 55 тысяч долларов для помощи пострадавшим от пожаров в России...

  16. В Турции взорван нефтепровод Киркук-Джейхан, двое погибших...

  17. В Боливии перевернулся автобус: 14 погибших, 20 раненых...

  18. Колумбия и Венесуэла помирились. Дипломатические отношения будут восстановлены...

  19. Первый этап американо-российских антитеррористических учений прошел успешно...

  20. Экс-директор NASA выжил в авиакатастрофе на Аляске, бывший сенатор погиб...

 

Случайные анекдоты

  • Виталия Калоева переводят из психиатрической клиники в тюрьму...

  • Оппозиция повезла по улицам Бангкока тела погибших накануне товарищей: убит 21 человек...

  • Премьер-министром Канады стал Пол Мартин...

  • Махмуд Аббас дал "Хамасу" еще три дня, но отказывается откладывать референдум...

  • На АЭС в Японии обнаружена пропажа урана...

    АНЕКДОТЫ

  • Ежедневные
  • Отобранные
  • Новые
  • Коллекция
    Архивы:
  • 1 2 3 4
  • 5 6 7 8 9
  • 10 11 12 13 14
  • 15 16 17 18 19
  • 20 21 22 23 24
  • 25 26 27 28 29
  • 30 31 32 33 34
  • 35 36 37 38 39
  • 40 41 42 43 44
  • 45 46 47 48 49
  • 50
    * * *
  • Истории
  • Афоризмы
  • Загадки


  • Terms of Service | Privacy Policy | Contact | Site Map
    Advertise with Us | Hosting | Site Map
    Russian America Top Rating © 2025 RussianAMERICA Holding
    All Rights Reserved • Contact