Gröbner bazuje w TCS?

Czy ktoś wie o ciekawych zastosowaniach baz Gröbnera w teoretycznej informatyce?

Podstawy Gröbnera są używane do rozwiązywania wielowymiarowych równań wielomianowych, co jest ogólnie trudnym problemem NP. Zastanawiałem się, czy użyto niektórych możliwych do rozwiązania specjalnych przypadków w celu zapewnienia wydajnych algorytmów / konstrukcji / dowodów w obszarach TCS lub powiązanych z TCS (kombinatoryka, teoria kodowania).

Obliczenia podstawowe Gröbnera, podczas gdy ogólnie EXPSPACE-complete, są w PSPACE ponad pierścieniami boolowskimi. Ma to zastosowania w sprawdzaniu modeli w celu zastąpienia BDD: Quoc-Nam Tran, „A PSPACE Algorytm do obliczania baz Groebnera w pierścieniach boolowskich”, Proc. WASET, tom. 35, listopad 2008, ISSN 2070-3740

[UWAGA] Wynik stwierdzający, że obliczenia podstawowe Groebnera są w PSPACE zamiast pierścieni boolowskich, wydaje się błędny, patrz Mark van Hoeij, podstawa Gröbnera w pierścieniach boolowskich nie jest P-SPACE , arXiv: 1502.07220 , 2015.

[UWAGA] Twierdzenie, że wynik stwierdzający, że obliczenia podstawowe Groebnera są w PSPACE ponad pierścieniami boolowskimi, wydaje się błędne, jest błędne. Autor myli obliczalność PSPACE z posiadaniem wielomianu. Funkcja PSPACE może mieć wykładniczo długi wynik.

Interesujący tom Springera dotyczy aplikacji baz Gröbnera w kodowaniu i kryptografii:

• Gröbner Bazy, kodowanie i kryptografia , / Sala, M .; Mora, T .; Perret, L .; Sakata, S .; Traverso, C. (red.).

Osobiście prowadzę badania nad algorytmami obliczania ideałów wielomianów lokalizatora błędów (dość dobrze znana koncepcja teorii kodowania, zwłaszcza dekodowania syndromu). W przypadku kodów z lokalizatorów błędów geometrii algowej ideał jest zwykle ideałem wielomianu z kilku zmiennych - w tym miejscu Bazy Gröbner odgrywają centralną rolę. W wyżej wymienionym tomie najbardziej interesującą częścią jest dla mnie opis algorytmu BMS S. Sakata i przegląd jego zastosowań do dekodowania kodów geometrii algebraicznej.

Właśnie słyszałem podczas warsztatów 8F

Oryginalny dowód na to, że kodowanie sieciowe może zostać zaimplementowane w sieci przepływowej, wykorzystuje podstawy Gröbnera.

Zasady Gröbnera zostały zastosowane do problemów związanych z ograniczeniem satysfakcji (patrz ten grant ). W tym momencie podstawowe techniki Gröbnera nie wydają się przydatne do stosowania ograniczenia satysfakcji, ponieważ konkurują one z dojrzałą heurystyką wyszukiwania, technikami egzekwowania spójności i wydajnymi propagatorami specjalnego przeznaczenia - nie wspominając już o dobrych rozwiązaniach SAT ogólnego przeznaczenia. Myślę jednak, że istnieją zdecydowanie zastosowania teoretyczne, które zostaną odkryte, zwłaszcza gdy podstawa Gröbnera ma rozsądną wielkość. Zobacz także artykuł Jeffersona, Jeavonsa, Greena i van Dongena, zaprezentowany na MACIS 2007 (wersja czasopisma: AMAI 67 359–382, 2013, doi: 10.1007 / s10472-013-9365-7 ), który omawia niektóre kwestie .

Użyłem podstawy Gröbnera, aby znaleźć krótki dowód nowego twierdzenia o dychotomii dla problemów #CSP na 3-regularnych wykresach z pojedynczą funkcją ograniczenia binarnego, która ma złożone wagi ( wersja arXiv ).

$f \sim g$$\#\operatorname{CSP}(f) = \#\operatorname{CSP}(g)$

Podstawa Gröbnera służy do konwersji z czterech początkowych zmiennych potrzebnych do zdefiniowania funkcji binarnej na sześć „zmiennych symetrycznych”, które są niezmienne w każdej klasie równoważności (zob. Sekcja D artykułu powiązanego powyżej). Jednak podstawa Gröbnera nie jest wspomniana w artykule, ponieważ jej jedynym celem była zautomatyzowana transformacja z czterech początkowych zmiennych do sześciu zmiennych symetrycznych w różnych wielomianach (co zostało wcześniej wykonane przez GroebnerBasis Mathematica ).

Poniższy artykuł może być postrzegany jako jedna aplikacja.

• Gunnar Carlsson, Gurjeet Singh, Afra Zomorodian: Computing Multidimensional Persistence. Journal of Computational Geometry, 1 (1) 2010, strony 72-100. http://jocg.org/index.php/jocg/article/view/19

Widzę, że autorzy wykorzystują algorytm Buchbergera jako podprogram i wykorzystują strukturę swojego problemu, aby udowodnić, że czas działania jest ograniczony wielomianowo.

Grant Passmore i inni piszą o nich w kontekście solverów SMT. Nie jestem ekspertem od podstaw Groebnera ani od solverów SMT, więc trudno mi ocenić, jak dobrze ten odnośnik odpowiada na twoje pytanie.

W dowód złożoności Clegg, Edmonds, Impagliazzo zaproponował zastosowanie zasad Gröbnera w celu obalenia CNF. Zdarzają się przypadki, w których ten system dowodowy przewyższa rozdzielczość wykładniczo, ale nie wydaje mi się, aby nastąpiła prawdziwa poprawa wydajności w ogólnych przypadkach.

$GF(2)$

Jednak Rachunek Wielomianowy nie był tak badany jak Rozdzielczość, dlatego dobrze przetestowana heurystyka nie jest dostępna.

Zobacz także to dla aplikacji w cryptanalysyis (niewiele o tym wiem).

$k$$k$

Bazy Grobnera są używane do najszybszych algorytmów dekodowania list dla kodów Reed-Solomon: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.320.1170&rep=rep1&type=pdf

Bazy Gröbner zostały z powodzeniem wykorzystane do rozwiązania ważnych problemów związanych z geometrią wielu widoków w wizji komputerowej .

Po http://arxiv.org/pdf/1502.05912.pdf czasem podstawa Grobnera jest używana do decydowania o izomorfizmie (gdy wykresy są kodowane przez układy równań). Ale łączy się to z wykorzystaniem zasady Grobnera w obaleniu CNFS.