An introduction to geometric complexity theory

zbMATH Open1358.68108arXiv1509.02503MaRDI QIDQ737196FDOQ737196

Authors: J. M. Landsberg 

Publication date: 9 August 2016

Published in: European Mathematical Society Newsletter (Search for Journal in Brave)

Abstract: I survey methods from differential geometry, algebraic geometry and representation theory relevant for the permanent v. determinant problem from computer science, an algebraic analog of the P v. NP problem.

Full work available at URL: https://arxiv.org/abs/1509.02503

Recommendations

• Geometric complexity theory: an introduction for geometers
• A geometric approach to complexity
• Geometric complexity theory. I: An approach to the P vs. NP and related problems
• Geometry and complexity theory
• Complexity of some geometric and topological problems
• scientific article; zbMATH DE number 1996521
• scientific article; zbMATH DE number 4014033
• Geometric complexity theory and matrix powering
• On the complexity of some geometric problems in unbounded dimension

zbMATH Keywords

complexity theoryP versus NP problem

Mathematics Subject Classification ID

General geometric structures on low-dimensional manifolds (57M50) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Cited In (12)

• \(\mathrm P \overset {?} {=} \mathrm{NP}\)
• Compatibility matrix method
• Geometric aspects of iterated matrix multiplication
• Title not available (Why is that?)
• Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
• Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
• On P vs. NP and geometric complexity theory: dedicated to Sri Ramakrishna
• An overview of mathematical issues arising in the geometric complexity theory approach to \(\mathbf{VP}\neq\mathbf{VNP}\)
• Some fast algorithms multiplying a matrix by its adjoint
• Geometry and complexity theory
• Geometric complexity theory: an introduction for geometers
• No occurrence obstructions in geometric complexity theory

This page was built for publication: An introduction to geometric complexity theory

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