I denna uppsats studerar vi algebraiska grenningsprogram (ABPs) med begränsningar i ordningen och antalet avläsningar av variabler i programmet. En ABP ges av en skiktad riktad acyklisk graf med källa s och sjunka t, vars kanter är märkta med variabler som tas från uppsättningen {x1, x2,. .., xn} eller fältkonstanter. Den beräknar summan av vikterna för alla stigar från s till t, där vikten av en stig definieras som produkten av egg-märkningar på banan. Med tanke på en permutation π av n variablerna, för en π-beställd ABP (π-OABP), för varje riktad väg p från s till t, kan en variabel visas som mest en gång på p, och den ordning i vilken variabler visas på p måste respektera π. En ABP A sägs vara läs r, om någon variabel visas som mest r gånger i A. Vårt huvudsakliga resultat hänför sig till problemet med identitetstester, d.v.s. Problemet med att avgöra om ett givet n-variatpolynom är identiskt med noll-polynomet eller inte. Över alla fält F och i den svarta lådan modellen, d.v.s. Med endast frågeåtkomst till polynomet har vi följande resultat: läs r π-OABP beräkningsbara polynom kan testas i DTIME[2 O(r log r·log 2 n log n) ]. I fall F är ett ändligt fält, ovanstående tidsbundna håller under förutsättning att identitetstestningsalgoritmen är tillåten att göra frågor till förlängningsfält av F. Vår nästa uppsättning av resultat undersöker de beräkningsmässiga begränsningarna för OABPs. Det visas att varje OABP-beräkning av bestämningsfaktorn eller permanent kräver storlek (2 n /n) och läs (2 n /n 2 ). Vi ger en multilinjär polynom p i 2n + 1 variabler över några specifikt utvalda fält G, så att alla OABP computing p måste läsa några variabel minst 2 n gånger. Vi bevisar en strikt separation för beräkningskraft av läsning (r − 1) och läsa r OABPs. Nämligen, vi visar att den elementära symmetriska polynom av grad r i n variabler kan beräknas med en storlek O (rn) läsa r OABP, men inte genom en läsning (r − 1) OABP, för alla 0 < 2r − 1 ≤ n. Slutligen ger vi ett exempel på en polynom p och två variabler order π = π ′, sådan att p kan beräknas av en read-once π-OABP, men där någon π ′ -OABP computing p måste läsa några variabel minst 2 n gånger.
I ett uppföljningsarbete REF utvidgade samma författare resultaten för läs-k ABPs där alla sökvägar läser variablerna i samma ordning, och återigen, k är en bunden på det totala antalet etiketter på vilka en variabel tillåts visas.
Deterministic Black-Box Identity Testing $\pi$-Ordered Algebraic Branching Programs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}