Вклад участника
Материал из DISCOPAL
- 16:24, 13 мая 2017 (разн. | история) . . (+2107) . . Н МТ не меняет вход/решение Сеилов (Новая страница: «Ответ: да. докажем лемму: если МТ, двигаясь по бесконечной вправо (или влево) ленте, запол…») (текущая)
- 16:23, 13 мая 2017 (разн. | история) . . (+278) . . Н МТ не меняет вход (Новая страница: «Существует ли МТ, проверяющая по описанию МТ М и входа x, что M не меняет состояние ленты в…») (текущая)
- 16:22, 13 мая 2017 (разн. | история) . . (+994) . . Н PH =? PSPACE/решение Сеилов (Новая страница: «в одной из задач было показано, что PH содержится в PSPACE. покажем, что это если PH = PSPACE, то пол…») (текущая)
- 16:21, 13 мая 2017 (разн. | история) . . (+284) . . Н PH =? PSPACE (Новая страница: «Показать, что если PH = PSPACE, то полиномиальная иерархия коллапсирует (совпадает с одним из…») (текущая)
- 03:53, 11 мая 2017 (разн. | история) . . (+1347) . . Н X-O в PSPACE/решение Сеилов (Новая страница: «*X-O в PSPACE На рабочей ленте для каждой клетки игровой доски заведем свою ячейку. Использ…») (текущая)
- 03:44, 11 мая 2017 (разн. | история) . . (+253) . . Н X-O в PSPACE (Новая страница: «Доказать, что язык всех выигрышных позиций в игре крестики-нолики на доске nxn принадлежи…») (текущая)
- 02:53, 11 мая 2017 (разн. | история) . . (+2560) . . Н Сильно связный граф NL-complete/Решение Сеилов (Новая страница: «*Сильно связный граф NL-complete Обозначим этот язык за M. проверим, что он в NL: Для этого нуж…») (текущая)
- 02:30, 11 мая 2017 (разн. | история) . . (+229) . . Н Сильно связный граф NL-complete (Новая страница: «Доказать, что язык всех сильно связных ориентированных графов - NL-полная задача. Катего…») (текущая)
- 01:58, 11 мая 2017 (разн. | история) . . (+2153) . . Н Бесконечное разрешимое подмножество бесконечного перечислимого множества/Решение (Новая страница: «*Бесконечное разрешимое подмножество бесконечного перечислимого множества Подзадач…») (текущая)
- 01:36, 11 мая 2017 (разн. | история) . . (+286) . . Н Бесконечное разрешимое подмножество бесконечного перечислимого множества (Новая страница: «Доказать, что в любом бесконечном перечислимом множестве можно выделить бесконечное ра…») (текущая)
- 08:02, 17 апреля 2017 (разн. | история) . . (+1232) . . Н Permission denied (Новая страница: «*Жадный алгоритм в задаче о рюкзаке/Задачи/Нижняя оценка точности модифицированного жа…»)
- 22:12, 16 апреля 2017 (разн. | история) . . (+1330) . . Н Permission denied (Новая страница: «*Жадный алгоритм в задаче о рюкзаке/Задачи/Greedy-Subset-Sum Пусть таким алгоритмом получили…»)
- 21:41, 16 апреля 2017 (разн. | история) . . (+1164) . . Н Permission denied (Новая страница: «*Полиномиальная иерархия/Задачи/PH collapse if PHC exists Пусть L - PH-полный язык. Значит, по опред…»)
- 21:16, 16 апреля 2017 (разн. | история) . . (+3092) . . Н Permission denied (Новая страница: «*Полиномиальная иерархия/Задачи/PH \subseteq PSPACE Задача аналогична задаче QSAT в PSPACE. По опре…»)
- 15:19, 16 апреля 2017 (разн. | история) . . (+76) . . Участник:Темирлан/Полиномиальная иерархия/Задачи/P^SAT=P^NP
- 15:11, 16 апреля 2017 (разн. | история) . . (+1161) . . Н Permission denied (Новая страница: «*Линейное программирование/Задачи/Выпуклый многогранник Для любого k в пространстве <…»)
- 14:46, 16 апреля 2017 (разн. | история) . . (+2657) . . Н Permission denied (Новая страница: «*Временная и пространственная сложность алгоритмов/Задачи/st-connectivity-log-diameter Следующая…»)
- 14:04, 16 апреля 2017 (разн. | история) . . (+2933) . . Н Permission denied (Новая страница: «*Временная и пространственная сложность алгоритмов/Задачи/QSAT in PSPACE Покажем, как можно…»)
- 13:01, 16 апреля 2017 (разн. | история) . . (+2544) . . Н Permission denied (Новая страница: «*Временная и пространственная сложность алгоритмов/Задачи/ex-limited-halt Есть утверждение:…»)
- 12:14, 16 апреля 2017 (разн. | история) . . (+36) . . Permission denied
- 12:13, 16 апреля 2017 (разн. | история) . . (+887) . . Н Permission denied (Новая страница: «*random-cloning-n-times Индукция по числу шагов: База очевидна (n = 0 шагов). Предположение: После n…»)
- 10:56, 16 апреля 2017 (разн. | история) . . (+2232) . . Н Permission denied (Новая страница: «*Временная и пространственная сложность алгоритмов/Задачи/ex-logspace-in-p Решение задачи а…»)
- 10:26, 16 апреля 2017 (разн. | история) . . (+1989) . . Н Permission denied (Новая страница: «*Временная_и_пространственная_сложность_алгоритмов/Задачи/PSPACE_in_EXPTIME Пусть язык L из PSP…»)
- 08:25, 5 апреля 2017 (разн. | история) . . (+491) . . Н Permission denied (Новая страница: «*Полиномиальные_сводимости_и_NP-полные_задачи._Классы_NP,_coNP,_NPC/Задачи/Tautology_in_coNP Да, т.к. з…»)
- 07:58, 4 апреля 2017 (разн. | история) . . (+1460) . . Н Permission denied (Новая страница: «Полиномиальные_сводимости_и_NP-полные_задачи._Классы_NP,_coNP,_NPC/Гамильтонов_граф для кажд…»)
- 22:01, 3 апреля 2017 (разн. | история) . . (+1649) . . Н Permission denied (Новая страница: «*Полиномиальная_иерархия/Задачи/compliment-in-ph По определению <latex>\Sigma_n</latex>: <latex>L\in \Sigma_n \Leftr…»)
- 21:16, 3 апреля 2017 (разн. | история) . . (+1904) . . Участник:Темирлан/Полиномиальная иерархия/Задачи/P^SAT=P^NP
- 21:03, 3 апреля 2017 (разн. | история) . . (+49) . . Н Участник:Темирлан/Полиномиальная иерархия/Задачи/P^SAT=P^NP (Новая страница: «По определению <latex>P^{NP}</latex>»)
- 20:53, 3 апреля 2017 (разн. | история) . . (+244) . . Н Permission denied (Новая страница: «Это множество n либо конечно, тогда оно разрешимо. Либо совпадает со всем натуральным ряд…»)
- 12:44, 23 марта 2017 (разн. | история) . . (+2011) . . Н Участник:Темирлан/Машина Тьюринга. Количество (Новая страница: «Определение из wiki: Конкретная машина Тьюринга задаётся перечислением элементов множест…») (текущая)
- 16:12, 16 марта 2017 (разн. | история) . . (+735) . . Н Permission denied (Новая страница: «*Жадный_алгоритм_в_задаче_о_рюкзаке/Задачи/Тупая_жадность_-_очень_плохо Пусть объем рю…»)
- 15:57, 16 марта 2017 (разн. | история) . . (+880) . . Н Участник:Темирлан/Вероятностная проверка тождеств/Задачи/Простая задача (Новая страница: «*Вероятностная_проверка_тождеств/Задачи/Простая_задача Числа <latex>1,2, \ldots p-1</latex> взаимн…»)
- 15:55, 16 марта 2017 (разн. | история) . . (+913) . . Н Permission denied (Новая страница: «*Вероятностные алгоритмы. Поиск решения уравнения за полиномиальное время нужно дока…»)
- 15:52, 16 марта 2017 (разн. | история) . . (+427) . . Н Permission denied (Новая страница: «<latex> P(E_1) = P(E_1|E_2)P(E_2) + P(E_1|\overline{E_2})P(\overline{E_2}) \leq P(E_1|\overline{E_2}) + P(E_2) \Leftrightarrow 0 \leq P(E_1|\overline{E_2})(1-P(\…»)
- 20:29, 15 марта 2017 (разн. | история) . . (+152) . . Н Обсуждение:PCP и неаппроксимируемость/c000109 (Новый комментарий от Темирлан: 13 слайд, опечатка: должно быть имеет долю невыполненных дизъюнктов >= \epsilon <!-- -->) (текущая)
- 22:16, 8 марта 2017 (разн. | история) . . (+80) . . Н Участник:Темирлан (Новая страница: «Сеилов Темирлан, студент 475 группы ФУПМ МФТИ») (текущая)