(no subject)
Кое кто, после длинного и не все время мирного обсуждения алгоритмов и структур данных для одной компьютерной задачки: "мне все еще удивительно, что ты можешь сказать что-то полезное по поводу алгоритмов."
"Ты думаешь это комплимент?" Обижаюсь я.
"Нет, но понимаешь, я уже столько много думал про эту задачу, что мне странно, что ты можешь сказать что-то правильное, до чего я еще не додумался."
И не знаю, то ли плакать, то ли смеяться. Ни у кого нет учебника по тезисам феминизма для особо закостенелых случаев?
-----------------
На следующий день обсуждаем всю ту же задачу. "Вот есть немного похожая, Hamiltonian path problem," говорю я, "и она NP-complete."
"Ну и что? Я уверен, что эта тоже NP-complete."
"Да? Тогда ее можно как-то изложить в виде Hamiltonian path или 3-Sat или чего-нибудь похожего из известных NP-complete задач."
"Чего это вдруг?"
"По определению NP-complete задач."
"Глупости," безапеляционно заявляет он мне.
Тут уж я не выдерживаю, передаю сидящего у меня на руках ребенка, открываю лежащую возле меня книгу и тыкаю в нее пальцем: "Cмотри!" А вот и не надо со мной спорить, когда у меня под боком оказывается "Introduction to Complexity Theory" by Sipser. Между прочим, я ее когда-то читала и понимала (пока читала).
A language B is said to be NP-complete if it satisfies two conditions: it is in NP and is polynomial time reducible to language A that is NP-complete (это не цитата, это по памяти -- сейчас под боком у меня книжки нет, а вставать лень).
"Ты думаешь это комплимент?" Обижаюсь я.
"Нет, но понимаешь, я уже столько много думал про эту задачу, что мне странно, что ты можешь сказать что-то правильное, до чего я еще не додумался."
И не знаю, то ли плакать, то ли смеяться. Ни у кого нет учебника по тезисам феминизма для особо закостенелых случаев?
-----------------
На следующий день обсуждаем всю ту же задачу. "Вот есть немного похожая, Hamiltonian path problem," говорю я, "и она NP-complete."
"Ну и что? Я уверен, что эта тоже NP-complete."
"Да? Тогда ее можно как-то изложить в виде Hamiltonian path или 3-Sat или чего-нибудь похожего из известных NP-complete задач."
"Чего это вдруг?"
"По определению NP-complete задач."
"Глупости," безапеляционно заявляет он мне.
Тут уж я не выдерживаю, передаю сидящего у меня на руках ребенка, открываю лежащую возле меня книгу и тыкаю в нее пальцем: "Cмотри!" А вот и не надо со мной спорить, когда у меня под боком оказывается "Introduction to Complexity Theory" by Sipser. Между прочим, я ее когда-то читала и понимала (пока читала).
A language B is said to be NP-complete if it satisfies two conditions: it is in NP and is polynomial time reducible to language A that is NP-complete (это не цитата, это по памяти -- сейчас под боком у меня книжки нет, а вставать лень).