We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Hilbert’s Nullstellensatz and NP-Complete Problems

00:00

Formale Metadaten

Titel
Hilbert’s Nullstellensatz and NP-Complete Problems
Alternativer Titel
Hilbert's Nullstellensatz, Grobner Bases, and NP-Complete Problems
Serientitel
Anzahl der Teile
28
Autor
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
Genre
Abstract
Combinatorial problems can be represented elegantly and efficiently by systems of polynomial equations. Those systems are either feasible or infeasible, depending on whether or not the underlying combinatorial property is present or not present. In this general survey talk, we will explore the infeasible polynomial systems and their associated combinatorial Nullstellensatz certificates, and we will also explore the feasible polynomial systems and their associated Grobner bases. Along the way, we will highlight some natural questions that arise and identify specific advantages/disadvantages of these methods. We will also suggest open problems and further research directions whenever possible.