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.