Dolne granice dla liniowego problemu satysfakcji

W SODA 1995 Jeff Erickson wykazały niższe granice liniowego spełnialności (sprawdzenie, czy niektóre -subset z n liczb rzeczywistych spełnia równanie liniowe o r zmiennych). Metoda dowodowa wykorzystuje nieskończenie małe i zasadę transferu Tarskiego .$r$$n$$r$

Czy ktoś mógłby wyjaśnić intuicję, jaką kryje się za tą trasą, aby udowodnić tę granicę? Jaka jest trudność w uzyskaniu bezpośredniego dowodu takiego jak ten: „Biorąc pod uwagę drzewo decyzyjne, które przyjmuje liczby rzeczywiste, oto, w jaki sposób możemy zbudować kontratak”.

I silnie sugerują czytania nowszą papier nawiązanie przez Ailon i Chazelle , który unika cały problem nieskończenie całkowicie. Jeśli chcesz trzymać się mojego artykułu, przeczytaj wersję czasopisma ( Chicago J Theoretical Computer Science 1999 ). Wersja SODA ma poważny błąd w sekcji 5 i (myślę) wersja czasopisma wyjaśnia bardziej wyraźnie główny dowód.

Rzeczywiście, głównym argumentem jest skonstruowanie drzewa decyzyjnego i zaprojektowanie kontrowersyjnych danych wejściowych, ale istnieją pewne techniczne problemy z robieniem tego, których unika się nieskończoności. Spójrz na dyskusję na dole pierwszej kolumny strony 2 i kontynuuj, co wyjaśnia to dość wyraźnie.