Teoria złożoności geometrycznej

Teoria złożoności geometrycznej (GCT) to program badawczy w teorii złożoności obliczeniowej zaproponowany przez Ketana Mulmuleya i Milinda Sohoniego. Celem programu jest odpowiedź na najsłynniejszy otwarty problem w informatyce – czy P = NP – poprzez wykazanie, że klasa złożoności P nie jest równa klasie złożoności NP .

Ideą tego podejścia jest przyjęcie i rozwinięcie zaawansowanych narzędzi geometrii algebraicznej i teorii reprezentacji (tj. teorii niezmienników geometrycznych ) w celu udowodnienia dolnych granic problemów. Obecnie program koncentruje się głównie na złożoności algebraicznej . Udowodnienie, że obliczenie permanentu nie może być skutecznie zredukowane do obliczenia wyznaczników , jest uważane za kamień milowy dla programu. Te problemy obliczeniowe można scharakteryzować za pomocą ich symetrii . Program ma na celu wykorzystanie tych symetrii do udowodnienia dolnych granic.

Podejście to jest uważane przez niektórych za jedyny realny obecnie aktywny program oddzielania P od NP . Jednak Ketan Mulmuley uważa, że ​​program, jeśli będzie wykonalny, prawdopodobnie zajmie około 100 lat, zanim rozwiąże problem P vs. NP .

Program jest realizowany przez kilku badaczy matematyki i informatyki teoretycznej. Jednym z powodów zainteresowania programem jest istnienie argumentów przemawiających za tym, że program unika znanych barier, takich jak relatywizacja i naturalne dowody na udowodnienie ogólnych dolnych granic.

Dalsza lektura

KD Mulmuley i M. Sohoni. Teoria złożoności geometrycznej I: podejście do P vs. NP i problemów pokrewnych. SIAM J. Komputer. 31(2), 496-526, 2001.

KD Mulmuley i M. Sohoni. Teoria złożoności geometrycznej II: w kierunku wyraźnych przeszkód dla osadzania między odmianami klas. SIAM J. Comput., 38 (3), 1175–1206, 2008.

KD Mulmuley, H. Narayanan i M. Sohoni. Teoria złożoności geometrycznej III: o decydowaniu o nieznikaniu współczynnika Littlewooda-Richardsona. J. Kombinacja algebraiczna. 36 (2012), no. 1, 103–110.

KD Mulmuley. Teoria złożoności geometrycznej V: Wydajne algorytmy normalizacji Noether. J.Amer. Matematyka soc. 30 (2017), nr. 1, 225-309. arXiv:1209.5993 [cs.CC]

KD Mulmuley. Geometric Complexity Theory VI: the flip via positivity., Raport techniczny, Wydział Informatyki, The University of Chicago, styczeń 2011.

Linki zewnętrzne

Pobrane z „ https://en.wikipedia.org/w/index.php?title=Geometric_complexity_theory&oldid=1131304331 ”