Report on "Mathematical Aspects of P vs. NP and its Variants."

arXiv1203.2888MaRDI QIDQ6231622FDOQ6231622

Publication date: 13 March 2012

Abstract: This is a report on a workshop held August 1 to August 5, 2011 at the Institute for Computational and Experimental Research in Mathematics (ICERM) at Brown University, Providence, Rhode Island, organized by Saugata Basu, Joseph M. Landsberg, and J. Maurice Rojas. We provide overviews of the more recent results presented at the workshop, including some works-in-progress as well as tentative and intriguing ideas for new directions. The main themes we discuss are representation theory and geometry in the Mulmuley-Sohoni Geometric Complexity Theory Program, and number theory and other ideas in the Blum-Shub-Smale model.

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Ordinary representations and characters (20C15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Representation theory for linear algebraic groups (20G05) Homogeneous spaces and generalizations (14M17) Compactifications; symmetric and spherical varieties (14M27) Polynomials and matrices (11C99)

This page was built for publication: Report on "Mathematical Aspects of P vs. NP and its Variants."

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6231622)