Podziel przez dwie funkcje w #P

Niech będzie liczbą całkowitą o wartości funkcja taka, że jest . Czy wynika z tego, że jest w ? Czy istnieją powody, by sądzić, że nie zawsze tak będzie? Jakieś referencje, o których powinienem wiedzieć? $F$ $2F$ $\#P$ $F$ $\#P$

Nieoczekiwanie sytuacja ta pojawiła się (ze znacznie większą stałą) dla funkcji dla której to stary otwarty problem. $F$ $F \in? \#P$

Uwaga: znam artykuł M. Ogiwara, L. Hemachandra, Teoria złożoności dla możliwych właściwości zamknięcia, w której zbadano pokrewny problem podziału na 2 (patrz Thm 3.13). Ich problem jest jednak inny, ponieważ definiują podział dla wszystkich funkcji za pośrednictwem operatora podłogi. To pozwoliło im na szybkie ograniczenie problemów z parzystością.

cc.complexity-theory complexity-classes counting-complexity

— Igor Pak
źródło

@Kaveh: Jeśli

jest funkcją

, a

jest funkcją wielozakresową , to

jest w

, ale

niekoniecznie (prawdopodobnie ). Na przykład wydaje się, że nie ma powodu, dla którego wszystkie nieujemne funkcje GapP powinny być w

, ale można je w ten sposób zredukować do

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$

— Emil Jeřábek wspiera Monikę

@JoshuaGrochow: Tak, to „Zaakceptuj, jeśli i tylko jeśli odgadłeś obu świadków 2F w porządku leksykograficznym”.

@JoshuaGrochow Jeśli wykonujesz podział bez funkcji podłogi, wówczas

spada do następującej klasy złożoności, którą właśnie zdefiniowałem, poprzez Twierdzenie 5.9 w książce TCTC.

istnieje predykat wielomianowy P i wielomian q taki, że dla wszystkich

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|$

Następnie należy pokazać, gdzie

należy do hierarchii złożoności. Mamy nadzieję, że przypadek

| 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}$

— Tayfun Pay

Jak trudno jest stwierdzić, czy funkcja w #PP jest zawsze parzysta? Spodziewam się, że to nierozstrzygalne.

— Peter Shor,

@PeterShor: To z pewnością nierozstrzygalne. Można wziąć maszynę, która akceptuje wtedy i tylko wtedy, gdy liczący świadek ma wszystkie 1s i taką samą długość jak wejście, a M zatrzymuje się dokładnie w krokach [tej długości].

Staram się dać intuicję, dlaczego uważam, że jest to mało prawdopodobne. Weź swój ulubiony problem w i przekształć go w problem w , np. Naszą funkcją może być liczba cykli hamiltonowskich na 3-regularnym wykresie wejściowym zawierającym pewną stałą krawędź. Z argumentem parzystości wiemy, że jest zawsze równa, dzięki czemu można określić i nie widzę powodu, dlaczego byłby w . $PPA$ $\sharp P$ $f$ $f$ $F:=f/2$ $F$ $\sharp P$

— domotorp
źródło

W porządku. Teraz jestem zdezorientowany. Czy

ma trzech cykli hamiltonowskich?

K_{4}

$K_4$

— Peter Shor

Okej ... Sprawdziłem. Twierdzenie jest takie, że każda krawędź pojawia się w parzystej liczbie (nieukierowanych) cykli hamiltonowskich na 3-regularnym wykresie, a nie, że istnieje parzysta liczba cykli hamiltonowskich ogółem. Tak więc właściwym problemem zliczania jest: biorąc pod uwagę trzy regularny wykres i krawędź

, niech

będzie liczbą cykli hamiltonowskich w

które przechodzą przez

. Czy

na #P?

e

$e$

f

$f$

G

$G$

e

$e$

F / 2

$F/2$

— Peter Shor

Rzeczywiście, zabawne, że nikt wcześniej tego nie zauważył ... Dodałem to.

— domotorp

Chociaż ogólnie zgadzam się z twoją intuicją, w tym przypadku myślę, że

może faktycznie być w #P: Niech e = (v_1, v_2) będzie krawędzią w G. Niech u, w będą sąsiadami v_1, którzy nie są t v_2. Następująca maszyna NP ma ścieżki akceptujące f / 2: zgadnij cykl Hamiltona, który zawiera parę krawędzi (u, v_1) i (v_1, v_2). (Chodzi o to, że dowód na parzystą parzystość tworzy bijection między takimi cyklami Ham. A tymi, które obejmują (w, v_1) i (v_1, v_2).) Aby intuicja działała, potrzebujesz czegoś w PPA, które przechodzi np. liczący się argument, który pozwala uniknąć łatwej biofuzji ...

f / 2

$f/2$

— Joshua Grochow

Fakt nie jest prawdą. Na przykład łatwo jest sprawdzić, czy zawodzi dla wszystkich połączonych 3-regularnych wykresów na 8 wierzchołkach (patrz lista en.wikipedia.org/wiki/Table_of_simple_cubic_graphs#8_nodes ), z wyjątkiem kostki (która jest przechodnia na krawędzi) .

— Emil Jeřábek wspiera Monikę