Мы знаем, что log ранга матрицы 0-1 является нижней границей детерминированной сложности связи, а log приблизительного ранга является нижней границей рандомизированной сложности связи. Наибольший разрыв между детерминированной коммуникационной сложностью и рандомизированной коммуникационной...
Это старая открытая проблема, справедлива ли теорема прямой суммы для детерминированной сложности коммуникации, то есть, является ли решение независимых случаев задачи в раз сложнее, чем решение одного случая. [FKNN95] показал следующие результаты:TTtTTt Отрицательный результат: есть частичная...
Предположим структуру в сложности коммуникации, где у нас есть два игрока A (вши) и B (ob) и R (eferee). А и Б не общаются напрямую друг с другом. В каждом раунде общения каждый из них отправляет сообщение (mAmAm_A, mBmBm_B) в R.R вычисляет две функции fA(mA,mB)fA(mA,mB)f_A(m_A,m_B) а также...
Каковы некоторые из лучших источников (книги и статьи), чтобы мотивировать и изучать сложность общения самостоятельно и в связи с ее отношением к теории вычислительной...
Пусть будет языком, и определим как тогда и только тогда, когда , Я ищу ссылку для:L⊆A∗L⊆A∗L \subseteq A^*fL:A∗×A∗→{0,1}fL:A∗×A∗→{0,1}f_L\colon A^* \times A^* \to \{0, 1\}fL(x,y)=1fL(x,y)=1f_L(x, y) = 1x⋅y∈Lx⋅y∈Lx\cdot y \in L Предложение. является регулярным, если детерминированная...