Вопрос о сложности подсчета прообраза

[Ales]

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

Задача может быть решена перебором за экспоненциальное время.

Но кажется она сложнее чем NP. Так ли это?

[Xaositect]

Ales в сообщении #332364 писал(а):

Пусть алгоритм работает ограниченное время,

Разъясните эту фразу, потому что, как мне кажется, от ее смысла может зависеть ответ на вопрос.

[Ales]

Xaositect в сообщении #332365 писал(а):

Ales в сообщении #332364 писал(а):

Пусть алгоритм работает ограниченное время,

Разъясните эту фразу, потому что, как мне кажется, от ее смысла может зависеть ответ на вопрос.

Число операций ограничено, например миллиард.
Сделал миллиард шагов и выдал ответ.

[Xaositect]

Сходу кажется, что можно как-то связать с классом #P, завтра с утра подумаю подробнее.

[Xaositect]

Получилось подумать сегодня. Поставленная задача почти в чистом виде #SAT.

Действительно, задача принадлежит классу #P: расссмотрим машину, которая недетерминированно порождает строку из нулей и единиц, а затем эмулирует нашу программу. Это NP-машина, количество принимающих путей равно количеству прообразов единицы.
Далее, задача #P-полна, так как к ней сводится #SAT (по формуле можно легко построить программу с ограниченным временем работы, которая эту формулу вычисляет)

По поводу сложности такой задачи можно сказать, что с помощью одного запроса к #P-полному оракулу можно решить любую задачу из полиномиальной иерархии (P, NP, coNP, и еще много). Однако для таких задач часто существуют хорошие приближенные рандомизированные алгоритмы

[Ales]

Xaositect в сообщении #332380 писал(а):

Поставленная задача почти в чистом виде #SAT.

По определению, я это и имел в виду.

Xaositect в сообщении #332380 писал(а):

ожно решить любую задачу из полиномиальной иерархии (P, NP, coNP, и еще много)

Интересно не сводится ли она к coNP. Что известно по этому вопросу?

[Xaositect]

Ales в сообщении #332406 писал(а):

Интересно не сводится ли она к coNP. Что известно по этому вопросу?

Во-первых, coNP - это класс задач распознавания, а #P - это класс задач поиска значения, так что понятие полиномиальной сводимости как оно обычно рассматривается (по Карпу), здесь неприменимо.
Во-вторых, определение старшего бита значения #P-функции - это класс PP (1, если у машины больше половины принимаюищих путей вычисления, 0 - если меньше). Это, скорее всего, более широкий класс, чем NP.
В-третьих, если рассматривать сводимость по Куку, т.е. класс $\mathrm{P}^{\sharp \mathrm{P}}$ всех полиномиальных машин, имеющих доступ к оракулу, решающему задачу #P-полную, то он содержит PH, а это класс, скорее всего, более широкий, чем NP.
http://qwiki.stanford.edu/wiki/Complexity_Zoo:P#pp
http://qwiki.stanford.edu/wiki/Complexity_Zoo:P#ph