Istnieje wiele problemów w kombinatorycznej teorii reprezentacji i geometrii algebraicznej, dla których nie jest znana formuła dodatnia. Myślę o kilku przykładach, ale pozwólcie, że obliczę współczynniki Kroneckera jako mój przykład. Zwykle pojęcie „formuły dodatniej” nie jest precyzyjnie zdefiniowane w kombinatorykach, ale z grubsza oznacza „opis jako liczność zbioru rozsądnie wyraźnego”. Ostatnio rozmawiałem z Jonaszem Blasiakiem i przekonał mnie, że właściwą definicją „pozytywnej formuły” jest #P . Zakładam, że na tej stronie nie muszę definiować #P.
Buergisser i Ikenmeyer pokazują, że współczynniki Kroneckera są #P trudne. (Są również zawsze pozytywne, ponieważ są mnożnikami produktów tensorowych.) Ale jestem dość pewien, że nikt nie zna sposobu ich obliczenia, który nawet doprowadziłby ich do #P.
Załóżmy więc, że miałbym faktycznie spróbować udowodnić, że współczynniki Kroneckera nie znajdują się w #P. Zakładam, że chciałbym założyć hipotezę złożoności teoretycznej, a następnie zredukować produkt Kroneckera do innego problemu, o którym wiadomo, że jest kompletny dla klasy większej niż #P.
Jakie przypuszczenie mogę założyć i do jakiego problemu mogę spróbować ograniczyć?
DODANO: Jak zauważono w komentarzach, Buergisser i Ikenmeyer pokazują, że współczynniki Kroneckera są w Gap-P, co jest dość zbliżone do #P. Wygląda więc na to, że pytania, które powinienem zadać, to (1) Jakie są niektóre problemy z uzupełnieniem luki P, które można prawdopodobnie zredukować i (2) jakie są szanse na wykazanie, że Gap-P nie jest #P? Wydaje mi się, że (2) należy podzielić na dwie części (2a). Czy eksperci uważają, że te klasy są inne? i (2b) czy istnieją jakieś strategie, które mogą to udowodnić?
Mam nadzieję, że ta edycja tego pytania nie jest niezadowolona.
źródło
Odpowiedzi:
Sugerowałbym przyjrzenie się właściwościom funkcji #P, które różnią się od funkcji Gap-P. Na przykład ustalenie, czy funkcja #P ma wartość zero, jest w ko-NP. Jeśli możesz wykazać, że ustalenie, czy współczynniki Kroneckera wynosi zero, jest trudne do uzyskania, to miałbyś „Współczynniki Kroneckera w #P implikuje UP w co-NP”, co jest mało prawdopodobne.
źródło
GapP to dokładnie zamknięcie #P odejmowane. Z drugiej strony, #P nie jest zamykane przy odejmowaniu, chyba że UP = PP. Wierzę, że to odpowiada na twoje pytania.
źródło
Kwestia obliczania Znaków nieredukowalnych reprezentacji grupy symetrycznej może być naturalnym kandydatem.
Myślę, że Charles Hepler pokazuje, że Gap-P jest kompletny, ale nie jestem pewien: link do pracy magisterskiej znajduje się na stronie https://dspace.ucalgary.ca/handle/1880/45530?mode=full
źródło