Skip to main content
MathOverflow

Return to Answer

added 2 characters in body
Source Link
user6976
user6976

In Sapir, Mark V.; Birget, Jean-Camille; Rips, Eliyahu Isoperimetric and isodiametric functions of groups. Ann. of Math. (2) 156 (2002), no. 2, 345–466 we proved that P=NP if and only if the word problem in every group with polynomial Dehn function can be solved in polynomial time by a deterministic Turing machine. Thus to show that P=NP one "only" needneeds to find an algebraic description of finitely presented groups with polynomial Dehn functionfunctions (similar to Gromov's description of groups with polynomial growth functions).

In Sapir, Mark V.; Birget, Jean-Camille; Rips, Eliyahu Isoperimetric and isodiametric functions of groups. Ann. of Math. (2) 156 (2002), no. 2, 345–466 we proved that P=NP if and only if the word problem in every group with polynomial Dehn function can be solved in polynomial time by a deterministic Turing machine. Thus to show that P=NP one "only" need to find an algebraic description of finitely presented groups with polynomial Dehn function (similar to Gromov's description of groups with polynomial growth functions).

In Sapir, Mark V.; Birget, Jean-Camille; Rips, Eliyahu Isoperimetric and isodiametric functions of groups. Ann. of Math. (2) 156 (2002), no. 2, 345–466 we proved that P=NP if and only if the word problem in every group with polynomial Dehn function can be solved in polynomial time by a deterministic Turing machine. Thus to show that P=NP one "only" needs to find an algebraic description of finitely presented groups with polynomial Dehn functions (similar to Gromov's description of groups with polynomial growth functions).

Source Link
user6976
user6976

In Sapir, Mark V.; Birget, Jean-Camille; Rips, Eliyahu Isoperimetric and isodiametric functions of groups. Ann. of Math. (2) 156 (2002), no. 2, 345–466 we proved that P=NP if and only if the word problem in every group with polynomial Dehn function can be solved in polynomial time by a deterministic Turing machine. Thus to show that P=NP one "only" need to find an algebraic description of finitely presented groups with polynomial Dehn function (similar to Gromov's description of groups with polynomial growth functions).