Является ли функция подсчета простых чисел # P-полной?

Напомним число простых чисел - функция подсчета простых чисел . Посредством «PRIMES in P» вычисление находится в #P. Проблема № P-завершена? Или, может быть, есть сложная причина полагать, что эта проблема не является # P-полной? $\pi(n)$ $\le n$ $\pi(n)$

PS Я понимаю, что это немного наивно, поскольку кто-то должен был изучить проблему и доказать / опровергнуть / предположить это, но я не могу найти ответ в литературе. Смотрите здесь, если вам интересно, почему я забочусь.

cc.complexity-theory counting-complexity nt.number-theory comp-number-theory primes Игорь Пак
источник

@MohsenGhorbani: Нет, не те же проблемы. Даже не похоже.

Игорь Пак

Не доказательства против, просто любопытно: знаем ли мы одну функцию которая # P-complete, которая действительно обрабатывает n как число? То есть мы всегда можем посмотреть на двоичное представление n и обработать эту двоичную строку как формулу или график SAT, но я хочу этого избежать.

f (n)

$f(n)$

Джошуа Грохов

@JoshuaGrochow «Естественные» (не NT) сложные проблемы, которые я знаю с одним параметром, все в # EXP-c. Пример такой проблемы: количество мозаичных квадратов квадрат с фиксированным набором плиток (то есть плитки не находятся на входе). Thm: существует st, эта проблема # EXP-c.

n \times n

$n \times n$

T

$T$

T

$T$

Игорь Пак

@Joshua Это довольно сильно связано с NP-полнотой , на которую, по-видимому, у нас еще нет однозначного ответа: cstheory.stackexchange.com/questions/14124/…

f (n)

$f(n)$

domotorp

Обратите внимание, что , поэтому был в #P со времен Миллера-Рабина.

# P^{B P P} = # P

$\mathrm{\#P^{BPP}=\#P}$

π

$\pi$

Эмиль Йержабек поддерживает Монику

Ответы:

Некоторые эвристические доказательства: насколько нам известно $\pi(n)$ выглядит как простая функция, исправленная случайными колебаниями. Таким образом, я ожидал бы, что многочленная машина с оракулом будет не сильнее, чем такая машина со случайным оракулом, и если случайный оракул добавит отдельный случайный оракул в получится с вероятностью 1 (здесь соответствует а - независимый случайный оракул). $\pi(n)$ $X$ $Y$ $\mathsf{P}$ $\#\mathsf{P}^X \not\subset \mathsf{P}^{XY}$ $Y$ $\pi(n)$ $X$

Джеффри Ирвинг
источник

Я нахожу последнее предложение вводящим в заблуждение. Хотя действительно , нам здесь действительно нужно , и мы не знаем, правда ли это. Фактически это эквивалентно .

\underset{X}{Pr} [{P P}^{X} \neq P^{X}] = 1

$\Pr_X[\mathrm{PP}^X\ne\mathrm{P}^X]=1$

\underset{X}{Pr} [P P ⊈ P^{X}] = 1

$\Pr_X[\mathrm{PP}\nsubseteq\mathrm{P}^X]=1$

P P \neq B P P

$\mathrm{PP\ne BPP}$

Эмиль Йержабек поддерживает Монику

@ EmilJeřábek: Конечно, но с точки зрения доказательства того, что не # P-complete, если бы можно было формально доказать, что если # P-complete, то PP = BPP, я бы воспринял это как довольно веское доказательство против # P-полноты ...

π (n)

$\pi(n)$

Джошуа Грохов

@JoshuaGrochow Я согласен с этим. Я просто не думаю, что результат на со случайным оракулом имеет значение.

P^{X} \neq {P P}^{X}

$\mathrm P^X\ne\mathrm{PP}^X$

Эмиль Йержабек поддерживает Монику

@ EmilJeřábek: Да, это хороший момент. Прежде чем я отредактирую, вы бы приняли в качестве доказательства тот факт, что

P^{X Y} \neq # P^{X}

$P^{XY} \ne \#P^X$ a дано два случайных оракула, которые, я думаю, мы знаем?

Джеффри Ирвинг

Мы знаем это?

Эмиль Йержабек поддерживает Монику