Страница 3 из 3 ПерваяПервая 123
Показано с 61 по 64 из 64
  1. #61

    По умолчанию

    Цитата Сообщение от Адепт_КАиП
    "Та самая NP-трудная задача" не не решается, а Вы ее не решаете (из-за экономии времени расчетов) - это совсем другое.
    Юлия, машина Тьюринга тоже вычисляет (проводит логическое доказательство), другое дело, что неизвестно завершаться ли эти вычисления за конечное время или нет. Об этом и речь!

  2. #62
    Член сообщества
    Регистрация
    03.12.2005
    Сообщений
    177

    По умолчанию

    Цитата Сообщение от Евгений
    Юлия, машина Тьюринга тоже вычисляет (проводит логическое доказательство), другое дело, что неизвестно завершаться ли эти вычисления за конечное время или нет. Об этом и речь!
    Опять пошел славный разговор, Фома с Еремой ничего бы не поняли :-(

    Только к полиномиальности (или нет) это не имеет прямого отношения (вернее, полиномиальный-то точно сходится, но и NP может сойтись). О другом разговор! Вы же не утверждаете, что если NP, то обязательно не сходится!
    Еще раз, Вы же можете без Ваших эвристик, а просто перебором решить NP-задачу (разумеется, не любую, а во-первых, разрешимую, во-вторых, имеющую в рассматриваемой области решение), если она небольшой размерности? Можно ответить Да/Нет? Или я что-то не так понимаю?

  3. #63

    По умолчанию

    Цитата Сообщение от Адепт_КАиП
    Вы же не утверждаете, что если NP, то обязательно не сходится!
    Юлия, утверждалось:
    Цитата Сообщение от Евгений
    То он, по-видимому, полиномиален по трудоемкости, т.е. не относится к классу NP-трудных. Pardon, не удержался...
    т.е. если процесс сходится, то он не NP. Заметьте, что это утверждение не совпадает с тем, которое Вы, Юлия, привели выше, - такого ведь никто и не утверждал.

  4. #64
    Член сообщества
    Регистрация
    03.12.2005
    Сообщений
    177

    По умолчанию

    Цитата Сообщение от Евгений
    Юлия, утверждалось:

    т.е. если процесс сходится, то он не Np. Заметьте, что это утверждение не совпадает с тем, которое Вы, Юлия, привели выше, - такого ведь никто и не утверждал.
    Нет, полиномиальность - это достаточное, но не необходимое условие сходимости. То есть слишком жесткое. Требует расширения и может быть, имхо, расширено (необходимое условие тут в принципе, опять же имхо, невозможно, так как неполнота не снимаема, но может быть более широкое достаточное условие). Только об этом и речь.

    "т.е. если процесс сходится, то он не Np" опять же неоднозначное утверждение. Если процесс сходится, то он, возможно, не Np, так как полиномиальные точно сходятся, а Np - неизвестно (надо уточнять, какие именно).

    Если я, разумеется, правильно понимаю эти Ваши Np (как "все" остальные", кроме полиномиальных).

Страница 3 из 3 ПерваяПервая 123

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •