Podziel przez dwie funkcje w #P

19

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

Nieoczekiwanie sytuacja ta pojawiła się (ze znacznie większą stałą) dla funkcji dla której F ? # P to stary otwarty problem. FF?#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ą.

Igor Pak
źródło
3
@Kaveh: Jeśli jest funkcją # P , a g ( y ) jest funkcją wielozakresową , to f ( g ( y ) ) jest w # P , ale g ( f ( x ) ) niekoniecznie (prawdopodobnie ). Na przykład wydaje się, że nie ma powodu, dla którego wszystkie nieujemne funkcje GapP powinny być w # P , ale można je w ten sposób zredukować do # P. f(x)#Pg(y)f(g(y))#Pg(f(x))#P#P
Emil Jeřábek wspiera Monikę
1
@JoshuaGrochow: Tak, to „Zaakceptuj, jeśli i tylko jeśli odgadłeś obu świadków 2F w porządku leksykograficznym”.
1
@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. U P P X = { L | istnieje predykat wielomianowy P i wielomian q taki, że dla wszystkich x , 1. x L | | { y | | y | q ( | x | ) P ( x , y ) } |PPUPPX={L|x1. xL||{y| 2. x L | | { y | | y | q ( | x | ) P ( x , y ) } | | 1 } Następnie należy pokazać, gdzie U P P X należy do hierarchii złożoności. Mamy nadzieję, że przypadek U P P X = P P|y|q(|x|)P(x,y)}||<1 2. xL||{y| |y|q(|x|)P(x,y)}||1}UPPXUPPX=PP
Tayfun Pay
2
Jak trudno jest stwierdzić, czy funkcja w #PP jest zawsze parzysta? Spodziewam się, że to nierozstrzygalne.
Peter Shor,
2
@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].

Odpowiedzi:

4

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 P , np. Naszą funkcją f może być liczba cykli hamiltonowskich na 3-regularnym wykresie wejściowym zawierającym pewną stałą krawędź. Z argumentem parzystości wiemy, że f jest zawsze równa, dzięki czemu można określić F : = f / 2 i nie widzę powodu, dlaczego F byłby w P .PPAPffF:=f/2FP

domotorp
źródło
2
W porządku. Teraz jestem zdezorientowany. Czy ma trzech cykli hamiltonowskich? K4
Peter Shor
5
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 f będzie liczbą cykli hamiltonowskich w G, które przechodzą przez e . Czy F / 2 na #P? efGeF/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
Joshua Grochow
2
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ę