Обсуждение:Сложностные классы. Вычисления с оракулом

ЭТО КАПЕЦ Кирилл Елагин 01:54, 24 апреля 2012 (GST)

Мда. Не могу не согласиться с предыдущим оратором. Претензии по содержанию

• Мы, помнится, вводили определения не через МТ, а через программы. Напиши их именно так, пожалуйста. А если уж пишешь МТ, уточняй детерминизм оной в определении, а не в конце статьи.
• А что такое оракул?

Претензии по оформлению.

• Используй, пожалуйста, нормальные шаблоны.
• Исправь минусы на тире.
• Если объединение по чему-то, то это что-то пишется строго под знаком объединения.
• Пропущенные запятые - это так, мелочи.

Я не понял, ЭТО зачтено или нет?

Если что, я остался при своём мнении, изложенном в первой строчке данного обсуждения. Кирилл Елагин 22:14, 31 мая 2012 (GST)

Действительно, стало заметно лучше ;). Но в первом определении всё ещё написан бред. «ограничение» — какое ещё ограничение? T — это просто время работы программы. С памятью аналогично. TS — вообще из другой оперы, поскольку это не число (время работы или объем памяти), а, как я понимаю из последующего использования, класс задач. И аргументы у него не программа и слово, а две функции. Ну и так дальше в том же духе… Кирилл Елагин 22:51, 2 июня 2012 (GST)

И вообще в TS надо еще написать пояснение про space-time tradeoff. Кирилл Елагин 22:53, 2 июня 2012 (GST)

Нина зачем-то проигнорировала примерно половину комментария. Я, наверное, слишком длинно написал… Кирилл Елагин 13:46, 3 июня 2012 (GST)

Кирилл, где ты взял space-time tradeoff? Я у Станка этого совсем не помню...

Я зато помню. Это было пояснение, почему TS(f,g) != DTIME(f) ∩ DSPACE(g). Собственно, надо нормально написать определение TS (желательно, наверное, с большой фигурной скобочкой), причем после DTIME и DSPACE. А потом нужно пояснить, почему, собственно, не равно пересечению. Если не помнишь, почему, спроси у Никиты — он точно помнит, поскольку больше всех возмущался по этому поводу. Кирилл Елагин 23:12, 3 июня 2012 (GST)

Раз уж мы работаем со строками на лентах, вместо «мощность x» лучше писать «длина x».

В определении оракула два объекта обозначены одной буквой A.

Дмитрий Шевченко 16:47, 4 июня 2012 (GST)