{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T14:41:57Z","timestamp":1773326517225,"version":"3.50.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,4,1]],"date-time":"2011-04-01T00:00:00Z","timestamp":1301616000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1017760"],"award-info":[{"award-number":["CCF-1017760"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,4]]},"abstract":"<jats:p>This article gives an overview of the geometric complexity theory (GCT) approach towards the P vs. NP and related problems focusing on its main complexity theoretic results. These are: (1) two concrete lower bounds, which are currently the best known lower bounds in the context of the P vs. NC and permanent vs. determinant problems, (2) the Flip Theorem, which formalizes the self-referential paradox in the P vs. NP problem, and (3) the Decomposition Theorem, which decomposes the arithmetic P vs. NP and permanent vs. determinant problems into subproblems without self-referential difficulty, consisting of positivity hypotheses in algebraic geometry and representation theory and easier hardness hypotheses.<\/jats:p>","DOI":"10.1145\/1944345.1944346","type":"journal-article","created":{"date-parts":[[2011,4,12]],"date-time":"2011-04-12T12:03:38Z","timestamp":1302609818000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["On P vs. NP and geometric complexity theory"],"prefix":"10.1145","volume":"58","author":[{"given":"Ketan D.","family":"Mulmuley","sequence":"first","affiliation":[{"name":"The University of Chicago, Chicago, IL"}]}],"member":"320","published-online":{"date-parts":[[2011,4,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490272"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_6"},{"key":"e_1_2_1_3_1","unstructured":"Atserias A. 2005. Non-uniform hardness for np via black-box adversaries. ECCC report 154. Atserias A. 2005. Non-uniform hardness for np via black-box adversaries. ECCC report 154."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Boppana R. and Sipser M. 1990. The complexity of finite functions. In Handbook of Theoretical Computer Science Volume A 757--804. Boppana R. and Sipser M. 1990. The complexity of finite functions. In Handbook of Theoretical Computer Science Volume A 757--804.","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Burgisser P. and Ikenmeyer C. 2010. Geometric complexity theory and tensor rank. arXiv:1011.1350 v1 {cs.CC}. Burgisser P. and Ikenmeyer C. 2010. Geometric complexity theory and tensor rank. arXiv:1011.1350 v1 {cs.CC}.","DOI":"10.1145\/1993636.1993704"},{"key":"e_1_2_1_6_1","unstructured":"B&amp;#252;rgisser P. Landsberg J. Manivel L. and Weyman J. 2009. An overview of mathematical issues arising in the geometric complexity theory approach to VP &amp;#8800; &amp;equals; VNP. arXiv: 0907.2850v1 {cs.CC}. B&amp;#252;rgisser P. Landsberg J. Manivel L. and Weyman J. 2009. An overview of mathematical issues arising in the geometric complexity theory approach to VP &amp;#8800; &amp;equals; VNP. arXiv: 0907.2850v1 {cs.CC}."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Deligne P. and Milne J. 1981. Hodge cycles motives and shimura varieties. Lecture Notes in Mathematics vol. 900 Springer Berlin Germany 101--228. Deligne P. and Milne J. 1981. Hodge cycles motives and shimura varieties. Lecture Notes in Mathematics vol. 900 Springer Berlin Germany 101--228.","DOI":"10.1007\/978-3-540-38955-2_4"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01247086"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.017"},{"key":"e_1_2_1_11_1","volume-title":"Sitzungsber Deutsch, Akad","author":"Frobenius G."},{"key":"e_1_2_1_12_1","volume-title":"Cambridge University Press","author":"Fulton W."},{"key":"e_1_2_1_13_1","unstructured":"Fulton W. and Harris J. 1991. Representation Theory A First Course. Springer Berlin Germany. Fulton W. and Harris J. 1991. Representation Theory A First Course. Springer Berlin Germany."},{"key":"e_1_2_1_14_1","unstructured":"Gr&amp;#246;tschel M. Lov&amp;#225;sz L. and Schrijver A. 1993. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag Berlin Germany. Gr&amp;#246;tschel M. Lov&amp;#225;sz L. and Schrijver A. 1993. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag Berlin Germany."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_39"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_2_1_18_1","volume-title":"Complexity of Computer Computations","author":"Karp R."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Karp R. and Ramachandran V. 1990. Parallel algorithms for shared memory machines. In Handbook of Theoretical Computer Science (vol. A). Elsevier 869--941. Karp R. and Ramachandran V. 1990. Parallel algorithms for shared memory machines. In Handbook of Theoretical Computer Science (vol. A). Elsevier 869--941.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"King R. Tollu C. and Toumazet F. 2004. Stretched littlewood-richardson coefficients and kostka coefficients. In Symmetry in Physics American Mathematical Society Providence 99--112. King R. Tollu C. and Toumazet F. 2004. Stretched littlewood-richardson coefficients and kostka coefficients. In Symmetry in Physics American Mathematical Society Providence 99--112.","DOI":"10.1090\/crmp\/034\/10"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00299-4"},{"key":"e_1_2_1_22_1","first-page":"175","article-title":"Honeycombs and sums of hermitian matrices","volume":"48","author":"Knutson A.","year":"2001","journal-title":"Notices Amer. Math. Soc."},{"key":"e_1_2_1_23_1","unstructured":"Kumar S. 2010. Geometry of orbits of permanents and determinants. arXiv:1007.1695 v1 {math.AG}. Kumar S. 2010. Geometry of orbits of permanents and determinants. arXiv:1007.1695 v1 {math.AG}."},{"key":"e_1_2_1_24_1","unstructured":"Landsberg J. Manivel L. and Ressayre N. 2010. Hypersurfaces with degenerate duals and the geometric complexity theory program. arXiv:1004.4802 v1 {math.AG}. Landsberg J. Manivel L. and Ressayre N. 2010. Hypersurfaces with degenerate duals and the geometric complexity theory program. arXiv:1004.4802 v1 {math.AG}."},{"key":"e_1_2_1_25_1","first-page":"115","article-title":"Universal sequential search problems","volume":"9","author":"Levin A.","year":"1973","journal-title":"Prob. Inf. Trans."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02564633"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1962-013-4"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(82)90048-2"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Mignon T. and Ressayre N. 2004. A quadratic bound for the determinant and permanent problem. Int. Math. Res. Not. 4241--4253. Mignon T. and Ressayre N. 2004. A quadratic bound for the determinant and permanent problem. Int. Math. Res. Not. 4241--4253.","DOI":"10.1155\/S1073792804142566"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794282930"},{"key":"e_1_2_1_31_1","volume-title":"Computer Science Department","author":"Mulmuley K."},{"key":"e_1_2_1_32_1","volume-title":"Computer Science Department","author":"Mulmuley K."},{"key":"e_1_2_1_33_1","unstructured":"Mulmuley K. 2010a. Explicit proofs and the flip. arXiv:1009.0246 v1 {cs.CC}. Mulmuley K. 2010a. Explicit proofs and the flip. arXiv:1009.0246 v1 {cs.CC}."},{"key":"e_1_2_1_34_1","volume-title":"Video of FOCS'10 http:\/\/techtalks.tv\/focs\/2010","author":"Mulmuley K.","year":"2010"},{"key":"e_1_2_1_35_1","volume-title":"The Computer Science Department","author":"Mulmuley K."},{"key":"e_1_2_1_36_1","volume-title":"V: On deciding nonvanishing of a generalized littlewood-richardson coefficient. Tech. rep., Department of Computer Science","author":"Mulmuley K.","year":"2007"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970038715X"},{"key":"e_1_2_1_38_1","volume-title":"III: On deciding positivity of littlewood-richardson coefficients. cs. ArXiv preprint cs. CC\/0501076 v1.","author":"Mulmuley K.","year":"2005"},{"key":"e_1_2_1_39_1","volume-title":"IV: Quantum group for the Kronecker problem. cs. ArXiv preprint cs. CC\/0703110.","author":"Mulmuley K.","year":"2007"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/080718115"},{"key":"e_1_2_1_41_1","volume-title":"Algebraic Geometry I: Complex Projective Varieties","author":"Mumford D."},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Mumford D. Fogarty J. and Kirwan F. 1994. Geometric Invariant Theory. Springer-Verlag Berlin Germany. Mumford D. Fogarty J. and Kirwan F. 1994. Geometric Invariant Theory. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-3-642-57916-5"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.04.003"},{"key":"e_1_2_1_45_1","first-page":"798","article-title":"Lower bounds on the monotone complexity of some Boolean functions","volume":"281","author":"Razborov A.","year":"1985","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Stanley R. 1987. Enumerative Combinatorics vol. 1. Cambridge University Press Cambridge UK. Stanley R. 1987. Enumerative Combinatorics vol. 1. Cambridge University Press Cambridge UK.","DOI":"10.1007\/978-1-4615-9763-6_1"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(83)80041-X"},{"key":"e_1_2_1_49_1","first-page":"406","article-title":"Relative bilinear complexity and matrix multiplication","volume":"376","author":"Strassen V.","year":"1987","journal-title":"J. Reigne Angnew. Math."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1944345.1944346","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1944345.1944346","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:30Z","timestamp":1750244370000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1944345.1944346"}},"subtitle":["Dedicated to Sri Ramakrishna"],"short-title":[],"issued":{"date-parts":[[2011,4]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["10.1145\/1944345.1944346"],"URL":"https:\/\/doi.org\/10.1145\/1944345.1944346","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4]]},"assertion":[{"value":"2009-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-04-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}