Свежие правки
Материал из 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») |