Złożoność topologiczna

W matematyce złożoność topologiczna przestrzeni topologicznej X (oznaczana również przez TC( X )) jest niezmiennikiem topologicznym ściśle związanym z problemem planowania ruchu , wprowadzonym przez Michaela Farbera w 2003 roku.

Definicja

Niech X będzie przestrzenią topologiczną i będzie przestrzenią wszystkich ${\ Displaystyle PX = \ {\ gamma: [0,1] \, \ to \, X \}}$ ciągłe ścieżki w X . Zdefiniuj rzut ${\ Displaystyle \ pi: PX \ do \, X \ razy X}$ przez ${\ Displaystyle \ pi (\ gamma) = (\ gamma (0), \ gamma (1))}$ . Złożoność topologiczna to minimalna liczba k taka, że

• istnieje otwarta pokrywa ${\ Displaystyle X \ razy X}$ , ${\ Displaystyle \ {U_ {i} \} _ {i = 1} ^ {k}$ }
• dla $_$ istnieje ${\ Displaystyle s_ {i}: \, U_ {i} \ do \, PX.}$ sekcja

Przykłady

• Złożoność topologiczna: TC( X ) = 1 wtedy i tylko wtedy, gdy X jest kurczliwy .
• Złożoność topologiczna sfery wynosi 2 dla n $nieparzystych$ i 3 parzystych . Na $przykład$ w przypadku okręgu możemy zdefiniować ścieżkę między dwoma punktami jako geodezyjną między , jeśli jest unikalna Dowolna para punktów na antypodach może być połączona drogą przeciwną do ruchu wskazówek zegara.
• Jeśli jest przestrzenią konfiguracyjną n różnych punktów w euklidesowej przestrzeni m , to ${\ Displaystyle F (\ mathbb {R} ^ {m}, n)}$

${\ Displaystyle TC (F (\ mathbb {R} ^ {m}, n)) = {\ rozpocząć {przypadki} 2n-1 i \ operatorname {dla \, \, {\ to {m}} \, \, nieparzyste } \\2n-2&\mathrm {for\,\,{\it {m}}\,\,parzyste.} \end{przypadki}}} Topologiczna$

• złożoność Butelka Kleina to 5.

• Farber, M. (2003). „Topologiczna złożoność planowania ruchu”. Dyskretna i obliczeniowa geometria . Tom. 29, nie. 2. s. 211–221.
• Armindo Costa: Topologiczna złożoność przestrzeni konfiguracyjnych , Ph.D. Teza, Durham University (2010), online