Pytania otagowane jako gct

Teoria złożoności geometrycznej

3
Wyjaśnienie w stylu Wikipedii teorii złożoności geometrycznej
Czy ktoś może przedstawić zwięzłe wyjaśnienie podejścia GCT Mulmuleya, zrozumiałe dla osób nie będących ekspertami? Wyjaśnienie, które byłoby odpowiednie dla strony Wikipedii na ten temat (która jest w tej chwili krótka). Motywacja: „Czytam” książkę Scotta Aaronsona Quantum Computing od czasów Demokryta z moim przyjacielem, który jest badaczem teorii strun. W …
1
Warunek do nauki GCT
Wydaje się, że Teoria Złożoności Geometrycznej wymaga dużej wiedzy na temat czystej matematyki, takiej jak geometria algebraiczna, teoria reprezentacji. Chociaż jestem studentem CS i NIE mam zajęć z bardzo abstrakcyjnej i czystej matematyki, interesuje mnie ten program. Czy istnieje lista „minimalnej wiedzy” do nauki tej teorii? Ta lista zawiera notatki …
2
Program GCT Mulmuleya
Czasami twierdzi się, że teoria złożoności geometrycznej Ketana Mulmuleya jest jedynym wiarygodnym programem do rozstrzygania otwartych pytań teorii złożoności, takich jak pytanie P vs. NP. Było wiele pozytywnych komentarzy od słynnych teoretyków złożoności na temat programu. Według Mulmuleya osiągnięcie pożądanych rezultatów zajmie dużo czasu. Wejście w ten obszar nie jest …
3
Czy implikuje ?
O ile rozumiem, program teorii geometrycznej złożoności próbuje oddzielić , udowadniając, że permament macierzy o złożonej wartości jest znacznie trudniejszy do obliczenia niż wyznacznik.VP≠VNPVP≠VNPVP \neq VNP Pytanie, które zadałem po przejrzeniu dokumentów GCT: Czy to natychmiast oznaczałoby , czy jest to tylko duży krok w kierunku tego celu?P≠NPP≠NPP \neq NP
2
Jak trudno jest zastosować podejście GCT Mulmuley-Sohoni do pokazania * znanych * separacji złożoności?
W tym poście Josh Grochow na blogu o złożoności relacjonuje ostatnie warsztaty poświęcone GCT, które odbyły się w lipcu w Princeton. Kilku uczestników argumentowało, że powinniśmy używać GCT do atakowania łatwiejszych problemów niż PP.\mathsf{P} vs. NPN.P.\mathsf{NP} w celu zbudowania intuicji i sprawdzenia, czy metoda ma potencjał. Pytanie, które mnie denerwuje: …
3
Konstruktywność w dowodzie naturalnym i złożoność geometryczna
Niedawno Ryan Willams udowodnił, że konstruktywność w naturalnym dowodzie jest nieunikniona, aby uzyskać separację klas złożoności: i . T C 0NEXPNEXP\mathsf{NEXP}TC0TC0\mathsf{TC}^{0} Konstruktywność w naturalnym dowodzie jest warunkiem, że wszystkie dowody kombinatoryczne w złożoności obwodu są spełnione i że możemy zdecydować, czy funkcja docelowa w (lub innej „twardej” klasie złożoności) ma …
4
Artykuły na temat związku między złożonością obliczeniową a geometrią / topologią algebraiczną?
Zastanawiałem się, jakie artykuły powinienem przeczytać, aby zrozumieć to pytanie Nieoczekiwane połączenie z innymi dziedzinami matematyki, takimi jak geometria algebraiczna lub wyższa kohomologia. Być może nawet dziedzina matematyki nie została jeszcze rozwinięta. Być może ktoś opracuje zupełnie nowy kierunek matematyki, aby poradzić sobie z pytaniem P kontra NP. -Od Fortnow …
2
W jaki sposób podejście geometryczne Mulmuleya-Sohoniego do wytwarzania dolnych granic unika tworzenia naturalnych dowodów (w sensie Razborowa-Rudicha)?
Dokładne sformułowanie tytułu należy do Ananda Kulkarniego (który zaproponował utworzenie tej strony). To pytanie zostało zadane jako przykładowe, ale jestem niesamowicie ciekawy. Wiem bardzo mało o geometrii algebraicznej, a tak naprawdę posiadam jedynie pobieżne, licencjackie rozumienie przeszkód występujących w pytaniu P / poli kontra NP (brak relatywizacji, brak algebrazowania, prawdopodobnie …
2
Status w dolnych granicach obwodu dla obwodów głębokości ograniczonych przez polilog
Złożoność obwodu złożoności jest jednym z głównych obszarów badań w ramach teorii złożoności obwodu. Ten temat ma swoje początki w wynikach takich jak „funkcja parzystości nie jest w ” i „funkcja mod nie jest obliczana przez ”, gdzie jest klasą języków rozstrzygalnych na podstawie niejednolitej, stałej głębokości, wielomianu, nieograniczonego wachlarza …
1
Lemat normalizacyjny Noether dla pól skończonych
Moje pytanie dotyczy twierdzeń 4.1 i 4.2 w „Teorii złożoności geometrycznej V” . Pierwsze twierdzenie mówi, że istnieje algorytm EXPSPACE do konstruowania hsop dlaΔ [ det , m ]Δ[det,m]\Delta[\text{det},m] (patrz definicje w artykule) na doC\mathbb{C} (w rzeczywistości na dowolnym algebraicznie zamkniętym polu o charakterystycznym zeru). Drugi zawiera probabilistyczny wielościeżkowy algorytm …
9 gct 
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.