Свежие правки
Материал из DISCOPAL
Ниже в хронологическом порядке перечислены последние изменения на страницах DISCOPAL.
6 марта 2021
09:51 | Участник:StasFomin/Bookmarks/Home/Appartment (разн. | история) . . (+1330) . . StasFomin (обсуждение | вклад) (Добавлена закладка Россия - социальное государство, против чуждых капиталистических ИИС, бирж и проч.?! :)): sporaw — ЖЖ) |
Н 03:00 | Участник:Павел Дидин/задача P NP BPP/решение (разн. | история) . . (+1392) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Поскольку класс $\mathcal{BPP}$ вложен в класс $\sum_2$, для решения задачи достаточно доказат…») |
Н 02:58 | Участник:Павел Дидин/задача P NP BPP (разн. | история) . . (+201) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Докажите, что если $\mathcal{P} = \mathcal{NP}$, то $\mathcal{P} = \mathcal{BPP}$. </latex> Категория:Предложенн…») |
Н 02:54 | Участник:Павел Дидин/задача о языке STOP/решение (разн. | история) . . (+1383) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> По каждому слову языка $L$ строим машину Тьюринга, которая работает как машина для ра…») |
Н 02:53 | Участник:Павел Дидин/задача о языке STOP (разн. | история) . . (+416) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Пусть язык $L\in\mathcal{NP}$. Покажите, что он полиномиально сводится (по Карпу) к языку $STOP$…») |
Н 02:48 | Участник:Павел Дидин/задача L factor/решение (разн. | история) . . (+1370) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Докажем $L_{factor} \in \mathcal{NP}$ \begin{proof} В качестве сертификата можно взять делитель $d$ числ…») |
Н 02:45 | Участник:Павел Дидин/задача L factor (разн. | история) . . (+382) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Покажите, что язык разложения на множители $$L_{factor} = \{(N,M)\in\mathbb{Z}^2 \mbox{ }|\mbox{ } 1<M<N\mbox{ и } N…») |
Н 02:41 | Участник:Павел Дидин/задача о ГП и ГЦ/решение (разн. | история) . . (+3042) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> \textbf{Сводимость ГЦ к ГП.} Возьмем произвольную вершину $A$. Добавим вершины $B$, $C$ и $D$ и…») |
Н 02:39 | Участник:Павел Дидин/задача о ГП и ГЦ (разн. | история) . . (+631) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Язык ГП состоит из описаний графов, имеющих гамильтонов путь.Язык ГЦ состоит из опи…») |
Н 02:33 | Участник:Павел Дидин/задача сводимость клик/решение (разн. | история) . . (+1609) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Пусть $n$ - количество вершин в графе. Возможны два случая. $1)$ $k < \frac n 2$. Тогда добавим…») |
Н 02:32 | Участник:Павел Дидин/задача сводимость клик (разн. | история) . . (+349) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Постройте сводимость по Карпу языка $(G, k)$ графов, в которых есть $k$-клика к языку гра…») |
Н 02:29 | Участник:Павел Дидин/задача NP=PSPACE/решение (разн. | история) . . (+531) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Если всякий $\mathcal{NP}$-трудный язык является $\mathcal{PSPACE}$-трудным, то $\mathcal{NP}$-полный язы…») |
Н 02:26 | Участник:Павел Дидин/задача NP=PSPACE (разн. | история) . . (+196) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Покажите, что если всякий $\mathcal{NP}$-трудный язык является $\mathcal{PSPACE}$-трудным, то $\mathcal{…») |
02:25 | (Журнал удалений) . . Павел Дидин (обсуждение | вклад) удалил страницу Участник:Павел Дидин/задача NP=PSPACE (содержимое: «<latex> Покажите, что если всякий $\mathcal{NP}$-трудный язык являет…» (единственным автором был Павел Дидин)) |
02:24 | (Журнал переименований) . . Павел Дидин (обсуждение | вклад) переименовал страницу Участник:Павел Дидин/задача NP= в Участник:Павел Дидин/задача NP=PSPACE |
Н 02:18 | Участник:Павел Дидин/задача о модификации 3-КНФ/решение (разн. | история) . . (+8055) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> \textbf{Решение пункта а)} Обозначим описанный выше язык выполнимых формул $3-VAR-3-SAT$. Для…») |
Н 02:14 | Участник:Павел Дидин/задача о модификации 3-КНФ (2 изменения | история) . . (+601) . . [Павел Дидин (2×)] | |
02:14 (текущ. | пред.) . . (+244) . . Павел Дидин (обсуждение | вклад) | ||
Н | 02:12 (текущ. | пред.) . . (+357) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Останется ли $3-SAT$ полной, если ограничиться формулами, в которых каждая переменная…») |
Н 02:01 | Участник:Павел Дидин/задача о разреженном языке/решение (разн. | история) . . (+1423) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Считаем входной алфавит бинарным (каждой букве можно сопоставить ее двоичный код).…») |
Н 01:59 | Участник:Павел Дидин/задача о разреженном языке (разн. | история) . . (+403) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Назовем язык $L$ разреженным, если для каждой длины $n$ в нём не более чем $p(n)$ слов тако…») |
Н 01:51 | Участник:Павел Дидин/задача l-eq-p-then-pspace-eq-exptime (разн. | история) . . (+1092) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Покажите, что если $DLOGSPACE = P$, то $PSPACE = EXPTIME$. \textbf{Решение.} По языку $L$ из класса $EXPTIME$ п…») |
5 марта 2021
Н 20:35 | Участник:Geralt z Rivii/task1 (разн. | история) . . (+345) . . Geralt z Rivii (обсуждение | вклад) (Новая страница: «*Временная и пространственная сложность алгоритмов/Задачи/SAT-in-LOGSPACE SAT является NP-пол…») |
Н 18:57 | Участник:Павел Дидин/задача о языке подслов/решение (разн. | история) . . (+1469) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Пусть $L$ состоит слов вида $\alpha\#\beta\#$, где $\alpha$~--~булев вектор, на котором истинна фор…») |
Н 18:56 | Участник:Павел Дидин/задача о языке подслов (2 изменения | история) . . (+495) . . [Павел Дидин (2×)] | |
18:56 (текущ. | пред.) . . (+83) . . Павел Дидин (обсуждение | вклад) | ||
Н | 18:55 (текущ. | пред.) . . (+412) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Определим для любого языка $L\subseteq\Sigma^*$ язык его подслов $subw(L) = \{u | \exists w, v \in \Sigma^* : wuv \i…») |
Н 18:48 | Участник:Павел Дидин/задача 3ESAT-NPC (разн. | история) . . (+887) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Покажите, что $3ESAT$ — $\mathcal{NP}$-полная задача. \textbf{Решение} Принадлежность классу $\mathc…») |
Н 18:22 | Участник:Павел Дидин/задача dlogspace-pspace-gap (3 изменения | история) . . (+2341) . . [Павел Дидин (3×)] | |
18:22 (текущ. | пред.) . . (+1) . . Павел Дидин (обсуждение | вклад) | ||
18:21 (текущ. | пред.) . . (-1) . . Павел Дидин (обсуждение | вклад) | ||
Н | 18:18 (текущ. | пред.) . . (+2341) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Покажите, что должно выполняться хотя бы одно из неравенств (несовпадений) классов…») |
15:28 | Участник:StasFomin/Bookmarks/Stegano (2 изменения | история) . . (+313) . . [StasFomin (2×)] | |
15:28 (текущ. | пред.) . . (+87) . . StasFomin (обсуждение | вклад) (Добавлена цитата к закладке Расширение и развертывание) | ||
15:24 (текущ. | пред.) . . (+226) . . StasFomin (обсуждение | вклад) (Добавлена закладка Расширение и развертывание) |
Н 11:33 | Участник:Павел Дидин/задача 3-КНФ→клика (разн. | история) . . (+2860) . . Павел Дидин (обсуждение | вклад) (Новая страница: «<latex> Получите сводимость как в Полиномиальные сводимости и $\mathcall{NP}$-полные задачи. Клас…») |
4 марта 2021
Н 13:24 | Участник:StasFomin/решение задачи 1 (разн. | история) . . (+277) . . StasFomin (обсуждение | вклад) (Новая страница: «* Временная и пространственная сложность алгоритмов/Задачи/SAT-in-LOGSPACE ---- ~~~~: Эй, а где р…») |
Н 13:01 | Участник:FominaAnna873 (разн. | история) . . (+64) . . FominaAnna873 (обсуждение | вклад) (Новая страница: «Фомина Анна Владимировна, группа 873») |
Н 12:15 | Участник:Fomberg (разн. | история) . . (+64) . . Fomberg (обсуждение | вклад) (Новая страница: «Фомберг Владислав Александрович 875») |
Н 12:02 | Участник:Ivan mipt (2 изменения | история) . . (+62) . . [Ivan mipt (2×)] | |
12:02 (текущ. | пред.) . . (+37) . . Ivan mipt (обсуждение | вклад) | ||
Н | 11:57 (текущ. | пред.) . . (+25) . . Ivan mipt (обсуждение | вклад) (Новая страница: «Степанов Иван») |
Н 12:02 | Участник:Ujify (2 изменения | история) . . (+33) . . [Ujify (2×)] | |
12:02 (текущ. | пред.) . . (+33) . . Ujify (обсуждение | вклад) | ||
Н | 12:01 (текущ. | пред.) . . (0) . . Ujify (обсуждение | вклад) (Создана пустая страница) |
Н 11:57 | Участник:Ar (3) (разн. | история) . . (+47) . . Ar (обсуждение | вклад) (Новая страница: «Людвиковская Анастасия 875») |
11:57 | (Журнал регистрации участников) . . [Ujify; Fomberg] | |
11:57 . . Участник создал учётную запись Ujify (обсуждение | вклад) | ||
11:57 . . Участник создал учётную запись Fomberg (обсуждение | вклад) |
Н 11:57 | Участник:Павел Дидин (2 изменения | история) . . (+31) . . [Павел Дидин (2×)] | |
11:57 (текущ. | пред.) . . (-25) . . Павел Дидин (обсуждение | вклад) | ||
Н | 11:48 (текущ. | пред.) . . (+56) . . Павел Дидин (обсуждение | вклад) (Новая страница: « Категория:Павел Дидин, Б05-873») |
Н 11:52 | Участник:Ar (2 изменения | история) . . (+47) . . [Ar (2×)] | |
11:52 (текущ. | пред.) . . (+16) . . Ar (обсуждение | вклад) | ||
Н | 11:47 (текущ. | пред.) . . (+31) . . Ar (обсуждение | вклад) (Новая страница: «Людвиковская А 875») |
Н 11:51 | Участник:Иван Тунёв (разн. | история) . . (+45) . . Иван Тунёв (обсуждение | вклад) (Новая страница: «Тунёв Иван Валерьевич, 875») |
Н 11:51 | Участник:USSRocker/dfsddsfsdfdsfdsf (2 изменения | история) . . (+47) . . [StasFomin (2×)] | |
11:51 (текущ. | пред.) . . (+42) . . StasFomin (обсуждение | вклад) | ||
Н | 11:50 (текущ. | пред.) . . (+5) . . StasFomin (обсуждение | вклад) (Новая страница: «11111») |
Н 11:49 | Участник:Srip09 (разн. | история) . . (+31) . . Srip09 (обсуждение | вклад) (Новая страница: «Алфимов Сергей 873») |
Н 11:47 | Участник:Dank0r (разн. | история) . . (+72) . . Dank0r (обсуждение | вклад) (Новая страница: «Корогодский Даниил Александрович, Б05-875») |
Н 11:47 | Участник:Bagurgl (разн. | история) . . (+29) . . Bagurgl (обсуждение | вклад) (Новая страница: «Скорик Сергей 875») |
Н 11:46 | Участник:Акобян Акоб (разн. | история) . . (+30) . . Акобян Акоб (обсуждение | вклад) (Новая страница: «Акобян Акоб Б05-875») |
Н 04:46 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/unary-in-p-then-time2kn-in-time2cn (разн. | история) . . (+344) . . StasFomin (обсуждение | вклад) (Новая страница: «Докажите, что если каждый унарный язык из NP также лежит в P, то то для любого языка из <m>T…») |
Н 04:40 | Унарный язык (разн. | история) . . (+128) . . StasFomin (обсуждение | вклад) (Новая страница: «Язык, где все слова из единиц (одного символа). https://en.wikipedia.org/wiki/Unary_language») |
Н 04:40 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/unary-in-p-then-exptime-nexp (разн. | история) . . (+187) . . StasFomin (обсуждение | вклад) (Новая страница: «Докажите, что если каждый унарный язык из NP также лежит в P, то EXPTIME=NEXP. Категория:Нереш…») |
Н 04:36 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/p-looks-unclosed-under-coding (2 изменения | история) . . (+242) . . [StasFomin (2×)] | |
04:36 (текущ. | пред.) . . (+58) . . StasFomin (обсуждение | вклад) | ||
Н | 04:36 (текущ. | пред.) . . (+184) . . StasFomin (обсуждение | вклад) (Новая страница: «K(L) — кодировка. Докажите, что класс P замкнут относительно кодировок тогда и только то…») |
Н 04:34 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/np-closed-under-coding (разн. | история) . . (+349) . . StasFomin (обсуждение | вклад) (Новая страница: «K(L) — кодировка. Докажите, что класс NP замкнут относительно кодировок. Т.е. покажите, чт…») |
Н 04:34 | Кодировка (разн. | история) . . (+573) . . StasFomin (обсуждение | вклад) (Новая страница: «Кодировка → преобразование (не обязательно однозначное), из одного алфавита в другой. Мо…») |
04:16 | Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ) (разн. | история) . . (-30) . . StasFomin (обсуждение | вклад) |
Н 03:40 | Временная и пространственная сложность алгоритмов/Задачи/l-eq-p-then-pspace-eq-exptime (2 изменения | история) . . (+176) . . [StasFomin (2×)] | |
03:40 (текущ. | пред.) . . (+58) . . StasFomin (обсуждение | вклад) | ||
Н | 03:40 (текущ. | пред.) . . (+118) . . StasFomin (обсуждение | вклад) (Новая страница: «Покажите, что если [https://en.wikipedia.org/wiki/L_(complexity) DLOGSPACE] = P, то PSPACE = EXPTIME.») |
Н 03:36 | Временная и пространственная сложность алгоритмов/Задачи/dlogspace-pspace-gap (2 изменения | история) . . (+463) . . [StasFomin (2×)] | |
03:36 (текущ. | пред.) . . (-1) . . StasFomin (обсуждение | вклад) | ||
Н | 03:36 (текущ. | пред.) . . (+464) . . StasFomin (обсуждение | вклад) (Новая страница: «Покажите, что должно выполняться хотя бы одно из неравенств (несовпадений) классов сложн…») |
Н 03:31 | Временная и пространственная сложность алгоритмов/Задачи/dtime-n2-is-closed-carp-reduction (разн. | история) . . (+401) . . StasFomin (обсуждение | вклад) (Новая страница: «* Класс сложности ''С'' замкнут относительно какой-то сводимости, если L→L' и <m>L' \in C</m>, то <m>L…») |
03:21 | (Журнал переименований) . . StasFomin (обсуждение | вклад) переименовал страницу Временная и пространственная сложность алгоритмов/замки и ключи в Временная и пространственная сложность алгоритмов/Задачи/замки и ключи без оставления перенаправления |
03:20 | Создать статью в данной категории (разн. | история) . . (+13) . . StasFomin (обсуждение | вклад) (Массовая правка: замена Временная и пространственная сложность алгоритмов/замки и ключи на Временная и пространственная сложность алго…) |
03:17 | (Журнал удалений) . . StasFomin (обсуждение | вклад) удалил страницу Временная и пространственная сложность алгоритмов/Задачи/ex-limited-haltБойко Дмитрий (содержимое: «#перенаправление Временная и пространственная сложность алгоритмов/З…» (единственным автором был USSRocker)) |
03:16 | Временная и пространственная сложность алгоритмов/Задачи/SAT-in-LOGSPACE (разн. | история) . . (+4) . . StasFomin (обсуждение | вклад) |
Н 03:13 | 3ESAT (2 изменения | история) . . (+150) . . [StasFomin (2×)] | |
03:13 (текущ. | пред.) . . (+37) . . StasFomin (обсуждение | вклад) | ||
Н | 03:13 (текущ. | пред.) . . (+113) . . StasFomin (обсуждение | вклад) (Новая страница: «Частный случай 3SAT, когда в каждой скобке ровно три литерала.») |
Н 03:12 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3ESAT-NPC (разн. | история) . . (+126) . . StasFomin (обсуждение | вклад) (Новая страница: «Покажите, что 3ESAT — NP-полная задача. Категория:Нерешенные задачи») |
03:10 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Порядок закачек — NPC (разн. | история) . . (+4) . . StasFomin (обсуждение | вклад) |
03:07 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/scheduling-ident-machines-in-npc (разн. | история) . . (+4) . . StasFomin (обсуждение | вклад) |
03:06 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/knights-np-complete (разн. | история) . . (+15) . . StasFomin (обсуждение | вклад) |
02:58 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/a^b eq c mod d in P (разн. | история) . . (+4) . . StasFomin (обсуждение | вклад) |
02:56 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/USUBSETSUM-IN-P (разн. | история) . . (+24) . . StasFomin (обсуждение | вклад) |
02:55 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/NTIME-NlogN-reduction-3SAT (разн. | история) . . (+24) . . StasFomin (обсуждение | вклад) |
02:55 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/MAX-CUT-NPC (разн. | история) . . (+24) . . StasFomin (обсуждение | вклад) |
02:54 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/HALT-and-NP (разн. | история) . . (+23) . . StasFomin (обсуждение | вклад) |
02:52 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/DHAM3 (разн. | история) . . (+4) . . StasFomin (обсуждение | вклад) |
02:50 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/QBEQ-NPC-NPC (2 изменения | история) . . (-5) . . [StasFomin (2×)] | |
02:50 (текущ. | пред.) . . (+4) . . StasFomin (обсуждение | вклад) | ||
02:50 (текущ. | пред.) . . (-9) . . StasFomin (обсуждение | вклад) |
02:46 | Участник:StasFomin/Bookmarks/Algorithms (2 изменения | история) . . (+198) . . [StasFomin (2×)] | |
02:46 (текущ. | пред.) . . (+101) . . StasFomin (обсуждение | вклад) (Добавлена закладка Index of /~irani/s18_cs262/HW) | ||
01:40 (текущ. | пред.) . . (+97) . . StasFomin (обсуждение | вклад) (Добавлена закладка solution1.pdf) |
Н 02:44 | Достижимость (разн. | история) . . (+186) . . StasFomin (обсуждение | вклад) (Новая страница: «Дан ориентированный граф ''G=(V,E)'', и узлы <m>u, v \in V</m>. Определить, есть ли путь ''u → v''. Кате…») |
02:08 | MAX-SAT: вероятностное округление/Задачи/max-sat-local-opt--1-2 (разн. | история) . . (-4) . . StasFomin (обсуждение | вклад) |
02:07 | MAX-CUT: вероятностное округление/Задачи/ex-min-maxmatching-1-2 (разн. | история) . . (-4) . . StasFomin (обсуждение | вклад) |
Н 02:06 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/strong-nmt-good-characterization (разн. | история) . . (+749) . . StasFomin (обсуждение | вклад) (Новая страница: «Пусть есть язык ''L'', для которого * есть некая МТ ''M'', возвращает «0», «1», «?». * для любого <m…») |
Н 01:36 | Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/conp-as-yes (разн. | история) . . (+578) . . StasFomin (обсуждение | вклад) (Новая страница: «Покажите, что язык L лежит в co-NP тогда и только тогда, если существует недетерминированна…») |
3 марта 2021
04:15 | Участник:StasFomin/Bookmarks/Stegano (разн. | история) . . (+726) . . StasFomin (обсуждение | вклад) (Добавлена закладка НОУ ИНТУИТ | Лекция | Стиль кодирования в Django) |
2 марта 2021
16:03 | Участник:StasFomin/Bookmarks/Home/Appartment (разн. | история) . . (+572) . . StasFomin (обсуждение | вклад) (Добавлена закладка Колония Навального как образец Системы: sapojnik — ЖЖ - Page 2) |
1 марта 2021
20:55 | Участник:StasFomin/Bookmarks/Home/Appartment (разн. | история) . . (+1470) . . StasFomin (обсуждение | вклад) (Добавлена закладка Родители vs руководители садов и школ: споры о детских прививках) |
11:49 | Участник:StasFomin/Bookmarks/Stegano (2 изменения | история) . . (+305) . . [StasFomin (2×)] | |
11:49 (текущ. | пред.) . . (+196) . . StasFomin (обсуждение | вклад) (Добавлена закладка Метрики в задачах машинного обучения / Блог компании Open Data Science / Хабр) | ||
03:34 (текущ. | пред.) . . (+109) . . StasFomin (обсуждение | вклад) (Добавлена закладка react-d3-tree - npm) |
11:41 | Участник:StasFomin/Bookmarks/Algorithms (3 изменения | история) . . (+500) . . [StasFomin (3×)] | |
11:41 (текущ. | пред.) . . (+271) . . StasFomin (обсуждение | вклад) (Добавлена закладка (13) (PDF) Solving the Quadratic Assignment Problem using the Swallow Swarm Optimization Problem) | ||
03:33 (текущ. | пред.) . . (+89) . . StasFomin (обсуждение | вклад) (Добавлена закладка react-d3-tree - npm) | ||
03:19 (текущ. | пред.) . . (+140) . . StasFomin (обсуждение | вклад) (Добавлена закладка anvaka/VivaGraphJS: Graph drawing library for JavaScript) |