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 .
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”.
Odpowiedzi:
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.
źródło
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.
źródło