Формализм концептуального -- абстракции и действительность

[Евгений]

"Та самая NP-трудная задача" не не решается, а Вы ее не решаете (из-за экономии времени расчетов) - это совсем другое.

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

[Адепт_КАиП]

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

Опять пошел славный разговор, Фома с Еремой ничего бы не поняли :-(

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

[Евгений]

Вы же не утверждаете, что если NP, то обязательно не сходится!

Юлия, утверждалось:

То он, по-видимому, полиномиален по трудоемкости, т.е. не относится к классу NP-трудных. Pardon, не удержался...

т.е. если процесс сходится, то он не NP. Заметьте, что это утверждение не совпадает с тем, которое Вы, Юлия, привели выше, - такого ведь никто и не утверждал.

[Адепт_КАиП]

Юлия, утверждалось:

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

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

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

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