I detta dokument studerar vi den roll som icke-adaptivitet spelar för att upprätthålla dynamiska datastrukturer. Ungefärligt är en datastruktur inte adaptiv om minnesplatserna den läser och/eller skriver vid behandling av en fråga eller uppdatering endast beror på frågan eller uppdateringen och inte på innehållet i tidigare lästa celler. Vi studerar sådana icke-adaptiva datastrukturer i cellsonden modellen. Denna modell är en av de minst restriktiva lägre bundna modellerna och i synnerhet, cellsond nedre gränser gäller för datastrukturer som utvecklats i den populära word-RAM-modellen. Tyvärr kommer denna generalitet till en hög kostnad: den högsta nedre gränsen som bevisats för alla datastrukturproblem är bara polylogaritmisk. Vårt huvudsakliga resultat är att visa att man faktiskt kan få polynom cellsond lägre gränser för icke-adaptiva datastrukturer. För att sprida mer ljus över den till synes inneboende polylogaritmiska nedre gränsbarriären studerar vi flera olika begrepp om icke-adaptivitet och identifierar viktiga egenskaper som måste hanteras om vi ska kunna bevisa polynomiska lägre gränser utan begränsningar på datastrukturerna. Slutligen presenterar våra resultat också en intressant koppling mellan datastrukturer och djup 2-kretsar. Detta gör att vi kan översätta förmodade problem med hårddatastruktur till bra kandidater för högre krets nedre gränser; i synnerhet inom området linjära kretsar för linjära operatörer. Med hjälp av lägre bundna bevis för datastrukturer i något mer restriktiva modeller presenterar vi också ett antal egenskaper hos linjära operatörer som vi anser är värda att undersöka i kretsens nedre gränser.
Brody och Larsen REF bevisar polynomala icke adaptiva nedre gränser för dynamiska datastrukturer.
Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}