Более сильные понятия униформизации?

Единственный пробел, который я всегда осознавал, что я на самом деле не понимаю, - это неравномерная и равномерная вычислительная сложность, где сложность схемы представляет собой неоднородную версию, а машины Тьюринга - это вещи, которые являются однородными. Я предполагаю, что «равномерный» - это способ ограничить класс алгоритмов, например, не допуская совершенно другой схемы для задачи с n переменными по сравнению с проблемой n + 1 переменных.

Мои вопросы: 1) там есть описание однородности только с точки зрения схем, и 2) возможно ли прийти с еще более сильной формой однородности и, таким образом, дать еще более ограниченное представление о том, какие эффективные (или сдержанные) алгоритмы в P есть?

Позднее пояснение: мое намерение в вопросе 2 касается ограниченного класса алгоритмов, который «практически» обладает той же силой, что и класс полиномиальных алгоритмов.

Я думаю, что ответ на первый вопрос отрицателен: схема имеет фиксированное количество входов, и, таким образом, IMO, мы можем говорить только о «семействах» схем, а не об одной единой схеме.

Что касается вашего второго вопроса, вы можете заметить, что существуют «однородные семейства цепей», описание которых генерируется машиной Тьюринга. То есть, пусть будет однородным семейством цепей, и пусть M будет машиной Тьюринга. Тогда для каждого п , [ С п ] = М ( 1 л ) , где [ С п ] обозначает описание C $\{C_n\}$$M$$n$$[C_n] = M(1^n)$$[C_n]$$C_n$ .

Ниже P есть несколько классов сложности, определяемых однородными семействами цепей. Например:

- это класс задач решения, разрешимыходнороднымилогическими схемами с полиномиальным числом вентилей и глубинойO( log i n).$\mathbf{NC}^i$$O(\log^i n)$

В дополнение к ответу Садека выше, когда мы рассматриваем классы схем, содержащиеся в P, можно также захотеть взглянуть на все более и более ограничительные понятия однородности.

Самым простым и наиболее известным понятием является P-однородность, которая является требованием наличия (детерминированной) машины Тьюринга M, которая создает схему $C_n$ во времени poly (n) (Суреш также говорит об этом). Более ограниченные версии единообразия пытаются ограничить мощность М еще больше. Например, существует также однородность Logspace, где теперь требуется M для запуска в пространстве O (log (n)).

Самым ограничительным понятием, о котором я знаю, является DLOGTIME-однородность, которая используется для небольших классов схем. Здесь машина М (теперь с произвольным доступом) имеет только время O (log n) и, следовательно, не может записать описание всей схемы. Наложенное условие состоит в том, что с учетом i и n M может записать i-й бит описания схемы за время O (log n).

Для получения дополнительной информации см. Следующую статью: Дэвид А. Микс Баррингтон, Нил Иммерман, Ховард Штраубинг: О однородности в NC¹. J. Comput. Сист. Sci. 41 (3): 274-306 (1990).

$n$$C_n$

Есть ли здесь описание однородности просто в плане схем?

$1$$f(|x|)$ где $f$ является функцией, вычисляемой любыми средствами, которые мы используем для описания схем.

С другой стороны, если нам разрешено ограничивать однородные схемы для определения схем, то ответ, очевидно, положительный. И мы можем использовать$FO$ (что равно $DLogTime$ и униформа $AC^0$) определить однородность. $FO$ концептуально очень близко к цепям.

Мне кажется, что главное здесь заключается в том, что нам нужна некоторая модель равномерных вычислений для определения однородности цепей, если описание цепей дается средствами, которые не являются однородными, схемы могут быть неоднородными.

1) Is there a description of uniformity just in terms of circuits?

[This is an edited version of my reply to the same question you asked on Dick Lipton's blog. Caveat: I'm not an expert.]

Yes (I think), of at least two different kinds:

a) The circuits are generatable by a Turing machine in polynomial time in the problem input size (as mentioned in some other replies). (I think this is the standard definition of the concept.)

Это охватывает любое семейство цепей, которое мы могли бы назвать унифицированным, но в качестве определения концепции P-времени оно просто сводит определение семейств цепей к определению на машинах Тьюринга, что может оказаться не тем, что вам нужно.

б) Если существует одномерный клеточный автомат, который развивает входные данные задачи для решения задачи (для решения проблемы решение будет одним битом в указанной ячейке относительно ячеек, содержащих входные данные, что является стабильным состоянием). CA), за полиномиальное время входного размера, это соответствует схеме, которая является периодической в ​​2D простым способом (одна повторяющаяся единица на ячейку на единицу времени), и состояние которой имеет значение только в квадратично большой области относительно ко времени решения.

Это очень особый вид семейства однородных цепей, но достаточный для решения всех проблем в P, поскольку машину Тьюринга можно легко закодировать как 1D CA. (Это также, кажется, удовлетворяет определению DLOGTIME-однородности, упомянутому в предыдущем ответе.)

(Это похоже на кодировки машин Тьюринга в виде цепей, упомянутых в ответах Гауэрса в блоге Липтона - фактически, один из них, вероятно, идентичен.)

Один из способов кодирования машины Тьюринга как 1D CA: в каждой ячейке мы представляем состояние ленты в одной точке, то состояние, которое было бы у головки машины Тьюринга, если бы она была здесь сейчас (значение которой не имеет значения, если ее здесь нет) и немного говорит, находится ли голова здесь сейчас. Ясно, что каждое такое состояние в момент времени t зависит только от его непосредственных состояний соседства в момент времени t-1, и это все, что нам нужно для того, чтобы это работало как CA.