Under de senaste åren har vi sett flera tillvägagångssätt till grafen isomorfism problem baserat på "generisk" matematisk programmering eller algebraiska (Gröbner bas) tekniker. För de flesta av dessa har lägre gränser fastställts. I själva verket har det visat sig att par av nonisomorphic CFI-grafer (introduced av Cai, Fürer, och Immerman 1992 som hårda exempel för combinatorial Weisfeiler-Leman algoritm) inte kan särskiljas med dessa matematiska algoritmer. Ett anmärkningsvärt undantag var algebraiska algoritmer över fältet F 2, för vilka ingen lägre gräns var känd. En annan, på något sätt ännu starkare, förhållningssätt till graf isomorfism testning bygger på att lösa system av linjära Diofantine ekvationer (det vill säga linjära ekvationer över heltalen), vilket är känt för att vara möjligt i polynom tid. Hittills har inga lägre gränser för detta tillvägagångssätt varit kända. Nedre gränser för algebraiska algoritmer kan bäst bevisas inom ramen för bevis komplexitet, där de kan uttryckas som nedre gränser för algebraiska bevissystem som Nullstellensatz eller (mer kraftfulla) polynomiska kalkyl. Vi ger nya hårda exempel för dessa system: familjer av par av icke-isomeriska grafer som är svåra att särskilja genom polynomiska kalkyl bevis samtidigt över alla primära fält, inklusive F 2, samt exempel som är svåra att skilja från system-av-linjär-Diofantine-ekvationer metod. I ett tidigare dokument konstaterade vi att CFI-graferna är nära relaterade till vad vi kallar "grupp CSPs": problem med begränsad tillfredsställelse där begränsningarna är medlemstester i någon coset av en undergrupp av en cartesian makt i en basgrupp (Z 2 i fallet med de klassiska CFI-grafer). Våra nya exempel är också baserade på grupp CSPs (för Abelian grupper), men här utökar vi CSPs med några icke-grupp begränsningar för att få ännu svårare fall för graf isomorfism.
För den senaste utvecklingen som relaterar tekniker av WL algoritmen till grupp-CSP (konstruerade tillfredsställelse problem där begränsningarna är cosets av en grupp) hänvisar vi till REF.
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}