Oto raczej odmienna aplikacja od tego, co mogłeś mieć na myśli. Programowanie liniowe ma wiele praktycznych zastosowań. Istnieje wiele algorytmów programowania liniowego, a te oparte na metodzie simpleks George'a Dantziga należą do najczęściej wdrażanych. Ważnym parametrem simplex jest tak zwana reguła przestawna. Victor Klee i George Minty zapewniają zestaw polytopów, na których zasada obrotu zaproponowana przez Dantzig wymagałaby wykładniczej liczby kroków obrotu. Od tego czasu odkryto przykłady wykładniczej dolnej granicy dla prawie każdej deterministycznej reguły przestawiania.
Simplex może jednak używać losowych reguł przestawnych. Gil Kalai w 1992 r. Wprowadził losową regułę obrotu i udowodnił, że reguła ta jest sub wykładnicza. Również w 1992 r. Micha Sharir i Emo Welzl zdefiniowali problemy typu LP, które obejmują standardowe programowanie liniowe, a wraz z Jiříem Matouškiem zaproponowali także losowe warianty simpleks i udowodnili podwykładnicze górne granice dla tego wariantu. Podwykładnicze dolne granice odkryto również w przypadku problemów typu LP, ale do około 2010 r. Nie było konkretnych przykładów programów liniowych, w których można by wykazać te dolne granice. Zobacz te dwa posty na blogu Gila Kalai, który opowiada o tej historii, związek z hipotezą Hirscha i linki do literatury.
Co to ma wspólnego z grami z parzystością? Aby skonfigurować połączenie, należy wykonać kilka kroków. Otwartym problemem w badaniach gier z parzystością do około 2009 r. Było ustalenie, czy pewne algorytmy iteracji polityki do rozwiązywania gier z parzystością mogą mieć charakter wykładniczy. Więcej informacji na ten temat można znaleźć w pracach Marcina Jurdzińskiego . Oliver Friedmann, począwszy od 2009 roku , pokazał przykłady gier parzystości, w których pewne algorytmy iteracji polityki wymagały czasu wykładniczego. Wykorzystując związek między grami parzystości a pewnymi problemami typu LP, wyprowadził sub wykładnicze dolne granice dla różnych reguł przestawnych dla simpleks. (Należy jednak zauważyć, że jeden z wyników dotyczących algorytmu losowego aspektu pokazali Oliver Friedmann, Thomas Hansen i Uri Zwick być w błędzie.)
Mam nadzieję, że zgodzisz się, że jest to dość fascynujący i przekonujący przykład zastosowania gier z parzystością.
Istnieje również bardziej bezpośrednia odpowiedź na twoje pytanie. Załóżmy, że chcemy zaprojektować dyskretny sterownik, który reguluje zachowanie niektórych układów fizycznych (termostat, fabryka chemiczna itp.) W zależności od stanu systemu i stanu środowiska. Pytanie, czy istnieje kontroler zapewniający gwarancje, których chce projektant, można sprowadzić do rozwiązania gier z parzystością. Możesz więc pomyśleć o grze parzystej pod względem systemów, środowisk i kontrolerów.
μμ