Vi bevisar nära-optimala kompromisser för kvantifier djup kontra antal variabler i första ordningen logik genom att uppvisa par av n-element strukturer som kan särskiljas med en k-variabel första ordningen mening men där varje sådan mening kräver kvantifier djup minst n  på (k/ log k). Våra kompromisser gäller också för första ordningens räknelogik, och genom den kända anslutningen till den k-dimensionella Weisfeiler-Leman algoritmen innebär nära-optimala lägre gränser på antalet förfining iterationer. En viktig komponent i vårt bevis är hårdhet kondensation teknik nyligen infördes av [Razborov '16] i samband med bevis komplexitet. Vi använder denna metod för att minska domänstorleken på relationsstrukturer samtidigt som vi upprätthåller det kvantifierdjup som krävs för att särskilja dem.
När det gäller gränser visade Berchholz och Nordström REF en lägre gräns för antalet iterationer av den k-dimensionella WL-algoritmen för finita strukturer.
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
{'venue': "LICS '16", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}