Title	Hilbert's Nullstellensatz, Grobner Bases, and NP-Complete Problems
Creator	Susan Margulies; Margulies, Susan
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2018-08-29T10:14
Description	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.
Extent	54.0 minutes
Subject	Mathematics; Computer Science; Mathematical Logic And Foundations; Theoretical Computer Science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: United States Naval Academy
Series	BIRS Workshop Lecture Videos (Oaxaca de Juárez (Mexico))
Date Available	2019-08-08
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0380350
URI	http://hdl.handle.net/2429/71256
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Researcher
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos

Hilbert's Nullstellensatz, Grobner Bases, and NP-Complete Problems Susan Margulies; Margulies, Susan

Description

Item Metadata

Item Media

Item Citations and Data

Rights