Показать сообщение отдельно
Старый 14.10.2009, 17:58   #12
Варвара
Full Member
 
Аватар для Варвара
 
Регистрация: 04.02.2009
Сообщений: 166
По умолчанию

Я доказываю как эквивалентность МТ и моей модели. Только начало формулирую по-другому, потому что мне эта эквивалентность не нужна, мне NP-трудность нужна. То есть говорю, что вот, сведем любую NP-полную задачу к нашей. NP-полная задача алгоритмически разрешима, значит, существует решающая ее МТ. И перевожу эту МТ в объекты моей модели, фактически, моделирую МТ в своих терминах. А в конце говорю, что так как мы взяли произвольную NP-полную и свели ее к нашей задаче, значит, наша задача NP-трудная. Вот так как-то!
---------
Ты прав, все истины просты, и открываются когда-то.
А правды нет. О ней мечты доверь наивности Сократа. (с)
Варвара вне форума   Ответить с цитированием
Реклама