Деление на две функции в #P

Пусть быть целым числом функция такая , что в . Из этого следует, что находится в ? Есть ли основания полагать, что это вряд ли сохранится? Любые ссылки, о которых я должен знать? $F$ $2F$ $\#P$ $F$ $\#P$

Несколько неожиданно возникла такая ситуация (с гораздо большей константой) для функции для которой - старая открытая проблема. $F$ $F \in? \#P$

Примечание: мне известна статья М. Огивара, Л. Хемачандра, Теория сложности для возможных свойств замыкания, где была изучена связанная проблема деления на 2 (см. Thm 3.13). Однако их проблема иная, поскольку они определяют разделение для всех функций через оператора пола. Это позволило им быстро сократить проблемы с паритетом.

cc.complexity-theory complexity-classes counting-complexity Игорь Пак
источник

@Kaveh: Если

- функция

, а

- функция поли-времени, то

находится в

, но

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

, но они сводятся к

таким образом.

f (x)

$f(x)$

# P

$\#P$

g (y)

$g(y)$

f (g (y))

$f(g(y))$

# P

$\#P$

g (f (x))

$g(f(x))$

# P

$\#P$

# P

$\#P$

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

@JoshuaGrochow: Да, это «Принять, если и только если вы угадали обоих свидетелей 2F в лексикографическом порядке».

@JoshuaGrochow Если вы выполняете деление без функции пола, то

сворачивается в следующий класс сложности, который я только что определил, с помощью теоремы 5.9 в книге TCTC.

существует предикат полиномиального времени P и такой многочлен q, что для всех

P P

${\bf PP}$

U P P X = {L |

${\bf UPPX} = \{ L |$

x

$x$

1.

$\bf 1.$

x \notin L \Rightarrow | | {y |

$x \not \in L \Rightarrow ||\{y|$

Затем необходимо показать, где

принадлежит в иерархии сложности. Следует надеяться, что

| y | \leq q (| x |) \land P (x, y)} | | < 1

$|y|\leq q(|x|) \wedge P(x,y)\}|| < 1$

2.

$\bf 2.$

x \in L \Rightarrow | | {y |

$x \in L \Rightarrow ||\{y|$

| y | \leq q (| x |) \land P (x, y)} | | \geq 1

$|y|\leq q(|x|) \wedge P(x,y)\}|| \geq 1$

}

$\}$

U P P X

${\bf UPPX}$

U P P X = P P

${\bf UPPX} = {\bf PP}$

Тайфун Пей

Насколько сложно определить, является ли функция в #PP всегда четной? Я ожидаю, что это неразрешимо.

Питер Шор

@PeterShor: Это, конечно, неразрешимо. Можно взять машину, которая принимает в том и только в том случае, если свидетель подсчета имеет все 1 с и ту же длину, что и вход, и M останавливается с точностью [этой длины] шагами.

Ответы:

Я пытаюсь выразить свою интуицию, почему я думаю, что это вряд ли удержит. Возьмите вашу любимую задачу в и преобразуйте ее в задачу в , например, наша функция может быть числом гамильтоновых циклов во входном 3-регулярном графе, содержащем некоторое фиксированное ребро. Из аргумента четности мы знаем , что всегда четно, так что вы можете определить , и я не вижу причин , почему будет в . $PPA$ $\sharp P$ $f$ $f$ $F:=f/2$ $F$ $\sharp P$

domotorp
источник

Ладно. Теперь я в замешательстве. Разве в

нет трех гамильтоновых циклов?

K_{4}

$K_4$

Питер Шор

Хорошо ... Я проверил. Теорема состоит в том, что каждое ребро появляется в четном количестве (неориентированных) гамильтоновых циклов в 3-регулярном графе, а не в том, что существует четное число полных гамильтоновых циклов. Таким образом, задача правильного счета такова: для трех регулярного графа и ребра

пусть

будет числом гамильтоновых циклов в

, проходящих через

. Является ли

в #P?

e

$e$

f

$f$

G

$G$

e

$e$

F / 2

$F/2$

Питер Шор

Действительно, забавно, что никто раньше не заметил ... Я добавил это.

domotorp

Хотя в целом я согласен с вашей интуицией, в этом случае я думаю, что

самом деле может быть в #P: пусть e = (v_1, v_2) будет ребром в G. Пусть u, w будут соседями v_1, которые не ' т v_2. Следующая машина NP имеет f / 2 принимающие пути: угадать цикл Гамильтона, который включает пару ребер (u, v_1) и (v_1, v_2). (Дело в том, что доказательство четной четности создает биекцию между такими циклами Хэма и теми, которые включают в себя (w, v_1) и (v_1, v_2).) Таким образом, чтобы интуиция работала, вам нужно что-то в PPA, которое проходит, например, счетный аргумент, или это позволяет избежать некоторой легкой биекции ...

f / 2

$f/2$

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

Факт не соответствует действительности. Например, легко проверить, что он не работает для всех связанных 3-регулярных графов на 8 вершинах (см. Список en.wikipedia.org/wiki/Table_of_simple_cubic_graphs#8_nodes для списка), за исключением куба (который является реберно-транзитивным) ,

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