Are there any computational problems in groups that are harder than P?












2












$begingroup$


There are several well known classes of groups for which the word problem, conjugacy etc. are solvable in polynomial time (hyperbolic, automatic).



Then there are several classes of groups like asynchronously automatic groups for which it is known that there is an exponential time algorithm to solve the word problem (and whether this can be improved to polynomial is open and conjectured as far as I'm aware).



Going several steps further, there is an algorithm to solve the word problem in one-relator groups in time not bounded by any finite tower of exponentials (and again it is open and conjectured whether this can be improved to P).



On the other, there are algorithms to solve word problems in pathological groups like the Baumslag-Gersten group:



$$G_{(1,2)} = langle a, b | a^{a^b}= a^2 rangle$$



in polynomial time. So even though general algorithms can be very bad, it is unknown whether there are group-specific algorithms for every group in a given class that solve the word problem quickly.



So my question is, are there any groups in which it is known that the word problem (or any other computational problem) is at least exponential, but still solvable? Maybe exp-complete? What are the approaches to proving such a thing?






gr.group-theory computational-complexity geometric-group-theory computational-group-theory word-problem







share|cite|improve this question









New contributor




MSL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$

















    2












    $begingroup$


    There are several well known classes of groups for which the word problem, conjugacy etc. are solvable in polynomial time (hyperbolic, automatic).



    Then there are several classes of groups like asynchronously automatic groups for which it is known that there is an exponential time algorithm to solve the word problem (and whether this can be improved to polynomial is open and conjectured as far as I'm aware).



    Going several steps further, there is an algorithm to solve the word problem in one-relator groups in time not bounded by any finite tower of exponentials (and again it is open and conjectured whether this can be improved to P).



    On the other, there are algorithms to solve word problems in pathological groups like the Baumslag-Gersten group:



    $$G_{(1,2)} = langle a, b | a^{a^b}= a^2 rangle$$



    in polynomial time. So even though general algorithms can be very bad, it is unknown whether there are group-specific algorithms for every group in a given class that solve the word problem quickly.



    So my question is, are there any groups in which it is known that the word problem (or any other computational problem) is at least exponential, but still solvable? Maybe exp-complete? What are the approaches to proving such a thing?






    gr.group-theory computational-complexity geometric-group-theory computational-group-theory word-problem







    share|cite|improve this question









    New contributor




    MSL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.







    $endgroup$















      2












      2








      2


      1



      $begingroup$


      There are several well known classes of groups for which the word problem, conjugacy etc. are solvable in polynomial time (hyperbolic, automatic).



      Then there are several classes of groups like asynchronously automatic groups for which it is known that there is an exponential time algorithm to solve the word problem (and whether this can be improved to polynomial is open and conjectured as far as I'm aware).



      Going several steps further, there is an algorithm to solve the word problem in one-relator groups in time not bounded by any finite tower of exponentials (and again it is open and conjectured whether this can be improved to P).



      On the other, there are algorithms to solve word problems in pathological groups like the Baumslag-Gersten group:



      $$G_{(1,2)} = langle a, b | a^{a^b}= a^2 rangle$$



      in polynomial time. So even though general algorithms can be very bad, it is unknown whether there are group-specific algorithms for every group in a given class that solve the word problem quickly.



      So my question is, are there any groups in which it is known that the word problem (or any other computational problem) is at least exponential, but still solvable? Maybe exp-complete? What are the approaches to proving such a thing?






      gr.group-theory computational-complexity geometric-group-theory computational-group-theory word-problem







      share|cite|improve this question









      New contributor




      MSL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.







      $endgroup$




      There are several well known classes of groups for which the word problem, conjugacy etc. are solvable in polynomial time (hyperbolic, automatic).



      Then there are several classes of groups like asynchronously automatic groups for which it is known that there is an exponential time algorithm to solve the word problem (and whether this can be improved to polynomial is open and conjectured as far as I'm aware).



      Going several steps further, there is an algorithm to solve the word problem in one-relator groups in time not bounded by any finite tower of exponentials (and again it is open and conjectured whether this can be improved to P).



      On the other, there are algorithms to solve word problems in pathological groups like the Baumslag-Gersten group:



      $$G_{(1,2)} = langle a, b | a^{a^b}= a^2 rangle$$



      in polynomial time. So even though general algorithms can be very bad, it is unknown whether there are group-specific algorithms for every group in a given class that solve the word problem quickly.



      So my question is, are there any groups in which it is known that the word problem (or any other computational problem) is at least exponential, but still solvable? Maybe exp-complete? What are the approaches to proving such a thing?






      gr.group-theory computational-complexity geometric-group-theory computational-group-theory word-problem




      gr.group-theory computational-complexity geometric-group-theory computational-group-theory word-problem






      share|cite|improve this question









      New contributor




      MSL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      share|cite|improve this question









      New contributor




      MSL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      share|cite|improve this question




      share|cite|improve this question








      edited 2 hours ago







      MSL













      New contributor




      MSL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked 3 hours ago









      MSLMSL

      114




      114




      New contributor




      MSL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      MSL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      MSL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






















          2 Answers
          2






          active

          oldest

          votes


















          3












          $begingroup$

          More or less what Andreas says is true but one must be careful in the encoding. In



          Isoperimetric and Isodiametric Functions of Groups,
          Mark V. Sapir, Jean-Camille Birget and Eliyahu Rips
          Annals of Mathematics
          Second Series, Vol. 156, No. 2 (Sep., 2002), pp. 345-466



          and



          Mark V. Sapir, Jean-Camille Birget and Eliyahu Rips
          Isoperimetric functions of groups and computational complexity of the word problem.
          Ann. of Math. (2) 156 (2002), no. 2, 467–518.



          groups with NP complete word problem are constructed and other similar results. See in particular, Corollary 1.1 of the first paper listed above.






          share|cite|improve this answer











          $endgroup$





















            2












            $begingroup$

            There are finitely presented groups whose word problem is undecidable. See, for example, https://en.wikipedia.org/wiki/Word_problem_for_groups .






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              True, what I really meant was among the groups whose word problem is solvable. Thanks, I'll edit my question!
              $endgroup$
              – MSL
              2 hours ago






            • 2




              $begingroup$
              @MSL I'd expect that the same method can handle the decidable case. Instead of coding into the presentation a Turing machine whose halting problem is undecidable, code one whose halting problem is decidable but takes a very long time to decide.
              $endgroup$
              – Andreas Blass
              2 hours ago











            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "504"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: true,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });






            MSL is a new contributor. Be nice, and check out our Code of Conduct.










            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f321547%2fare-there-any-computational-problems-in-groups-that-are-harder-than-p%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            3












            $begingroup$

            More or less what Andreas says is true but one must be careful in the encoding. In



            Isoperimetric and Isodiametric Functions of Groups,
            Mark V. Sapir, Jean-Camille Birget and Eliyahu Rips
            Annals of Mathematics
            Second Series, Vol. 156, No. 2 (Sep., 2002), pp. 345-466



            and



            Mark V. Sapir, Jean-Camille Birget and Eliyahu Rips
            Isoperimetric functions of groups and computational complexity of the word problem.
            Ann. of Math. (2) 156 (2002), no. 2, 467–518.



            groups with NP complete word problem are constructed and other similar results. See in particular, Corollary 1.1 of the first paper listed above.






            share|cite|improve this answer











            $endgroup$


















              3












              $begingroup$

              More or less what Andreas says is true but one must be careful in the encoding. In



              Isoperimetric and Isodiametric Functions of Groups,
              Mark V. Sapir, Jean-Camille Birget and Eliyahu Rips
              Annals of Mathematics
              Second Series, Vol. 156, No. 2 (Sep., 2002), pp. 345-466



              and



              Mark V. Sapir, Jean-Camille Birget and Eliyahu Rips
              Isoperimetric functions of groups and computational complexity of the word problem.
              Ann. of Math. (2) 156 (2002), no. 2, 467–518.



              groups with NP complete word problem are constructed and other similar results. See in particular, Corollary 1.1 of the first paper listed above.






              share|cite|improve this answer











              $endgroup$
















                3












                3








                3





                $begingroup$

                More or less what Andreas says is true but one must be careful in the encoding. In



                Isoperimetric and Isodiametric Functions of Groups,
                Mark V. Sapir, Jean-Camille Birget and Eliyahu Rips
                Annals of Mathematics
                Second Series, Vol. 156, No. 2 (Sep., 2002), pp. 345-466



                and



                Mark V. Sapir, Jean-Camille Birget and Eliyahu Rips
                Isoperimetric functions of groups and computational complexity of the word problem.
                Ann. of Math. (2) 156 (2002), no. 2, 467–518.



                groups with NP complete word problem are constructed and other similar results. See in particular, Corollary 1.1 of the first paper listed above.






                share|cite|improve this answer











                $endgroup$



                More or less what Andreas says is true but one must be careful in the encoding. In



                Isoperimetric and Isodiametric Functions of Groups,
                Mark V. Sapir, Jean-Camille Birget and Eliyahu Rips
                Annals of Mathematics
                Second Series, Vol. 156, No. 2 (Sep., 2002), pp. 345-466



                and



                Mark V. Sapir, Jean-Camille Birget and Eliyahu Rips
                Isoperimetric functions of groups and computational complexity of the word problem.
                Ann. of Math. (2) 156 (2002), no. 2, 467–518.



                groups with NP complete word problem are constructed and other similar results. See in particular, Corollary 1.1 of the first paper listed above.







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited 2 hours ago

























                answered 2 hours ago









                Benjamin SteinbergBenjamin Steinberg

                23.1k265124




                23.1k265124























                    2












                    $begingroup$

                    There are finitely presented groups whose word problem is undecidable. See, for example, https://en.wikipedia.org/wiki/Word_problem_for_groups .






                    share|cite|improve this answer









                    $endgroup$













                    • $begingroup$
                      True, what I really meant was among the groups whose word problem is solvable. Thanks, I'll edit my question!
                      $endgroup$
                      – MSL
                      2 hours ago






                    • 2




                      $begingroup$
                      @MSL I'd expect that the same method can handle the decidable case. Instead of coding into the presentation a Turing machine whose halting problem is undecidable, code one whose halting problem is decidable but takes a very long time to decide.
                      $endgroup$
                      – Andreas Blass
                      2 hours ago
















                    2












                    $begingroup$

                    There are finitely presented groups whose word problem is undecidable. See, for example, https://en.wikipedia.org/wiki/Word_problem_for_groups .






                    share|cite|improve this answer









                    $endgroup$













                    • $begingroup$
                      True, what I really meant was among the groups whose word problem is solvable. Thanks, I'll edit my question!
                      $endgroup$
                      – MSL
                      2 hours ago






                    • 2




                      $begingroup$
                      @MSL I'd expect that the same method can handle the decidable case. Instead of coding into the presentation a Turing machine whose halting problem is undecidable, code one whose halting problem is decidable but takes a very long time to decide.
                      $endgroup$
                      – Andreas Blass
                      2 hours ago














                    2












                    2








                    2





                    $begingroup$

                    There are finitely presented groups whose word problem is undecidable. See, for example, https://en.wikipedia.org/wiki/Word_problem_for_groups .






                    share|cite|improve this answer









                    $endgroup$



                    There are finitely presented groups whose word problem is undecidable. See, for example, https://en.wikipedia.org/wiki/Word_problem_for_groups .







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered 3 hours ago









                    Andreas BlassAndreas Blass

                    57k7135218




                    57k7135218












                    • $begingroup$
                      True, what I really meant was among the groups whose word problem is solvable. Thanks, I'll edit my question!
                      $endgroup$
                      – MSL
                      2 hours ago






                    • 2




                      $begingroup$
                      @MSL I'd expect that the same method can handle the decidable case. Instead of coding into the presentation a Turing machine whose halting problem is undecidable, code one whose halting problem is decidable but takes a very long time to decide.
                      $endgroup$
                      – Andreas Blass
                      2 hours ago


















                    • $begingroup$
                      True, what I really meant was among the groups whose word problem is solvable. Thanks, I'll edit my question!
                      $endgroup$
                      – MSL
                      2 hours ago






                    • 2




                      $begingroup$
                      @MSL I'd expect that the same method can handle the decidable case. Instead of coding into the presentation a Turing machine whose halting problem is undecidable, code one whose halting problem is decidable but takes a very long time to decide.
                      $endgroup$
                      – Andreas Blass
                      2 hours ago
















                    $begingroup$
                    True, what I really meant was among the groups whose word problem is solvable. Thanks, I'll edit my question!
                    $endgroup$
                    – MSL
                    2 hours ago




                    $begingroup$
                    True, what I really meant was among the groups whose word problem is solvable. Thanks, I'll edit my question!
                    $endgroup$
                    – MSL
                    2 hours ago




                    2




                    2




                    $begingroup$
                    @MSL I'd expect that the same method can handle the decidable case. Instead of coding into the presentation a Turing machine whose halting problem is undecidable, code one whose halting problem is decidable but takes a very long time to decide.
                    $endgroup$
                    – Andreas Blass
                    2 hours ago




                    $begingroup$
                    @MSL I'd expect that the same method can handle the decidable case. Instead of coding into the presentation a Turing machine whose halting problem is undecidable, code one whose halting problem is decidable but takes a very long time to decide.
                    $endgroup$
                    – Andreas Blass
                    2 hours ago










                    MSL is a new contributor. Be nice, and check out our Code of Conduct.










                    draft saved

                    draft discarded


















                    MSL is a new contributor. Be nice, and check out our Code of Conduct.













                    MSL is a new contributor. Be nice, and check out our Code of Conduct.












                    MSL is a new contributor. Be nice, and check out our Code of Conduct.
















                    Thanks for contributing an answer to MathOverflow!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid …



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f321547%2fare-there-any-computational-problems-in-groups-that-are-harder-than-p%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    -

                    Popular posts from this blog

                    الفوسفات في المغرب

                    Image
                    قطار ينقل فوسفات من منطقة خريبكة متجه نحو الدار البيضاء. ديار عمال بمصانع الفوسفات بمدينة آسفي. المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (أغسطس 2015) الفوسفات في المغرب هو ثالث مصدر عالمي للفوسفات، ويتوفر المغرب على %75 من الاحتياطي العالمي  [بحاجة لمصدر] ويتوزع بنسب متفاوتة بين عدة مناطق أساسية وهي: وادي زم بن جرير بوكراع خريبكة اليوسفية أولاد عبدون كنتور واد الذهب مستقلة. هذه الأخيرة لم تفتح بعد للاستغلال. الصادرات الحامض الفوسفوري P205 تمتص الهند %50 من ا لصادرات الإجمالية آسيا (دون روسيا)%59 أوروبا %30 أمريكا اللاتينية %11 أسمدة صلبة أوروبا 38 % أمريكا اللاتينية %30 آسيا (دون روسيا) 22 % أستراليا 9 % بوابة المغرب هذه بذرة مقالة عن علم الاقتصاد أو موضوع متعلق به بحاجة للتوسيع. شارك في تحريرها. This page is only for reference, If you need detailed information, please check here
                    Read more

                    Four equal circles intersect: What is the area of the small shaded portion and its height

                    Image
                    3 $begingroup$ In terms of $R$ which is the radius of all four circles, what is the area of the intersection region of these four equal circles and the height of the marked arrow in the figure? The marked arrow is along the line CD, also the midpoint of all the circles are points A, B, C and D. Looking for a very short intuitive solution. I have checked similar questions on this site for example this and this. geometry circle share | cite | improve this question edited 2 hours ago Abdulhameed asked 2 hours ago ...
                    Read more

                    جامعة ليفربول

                    Image
                    جامعة ليفربول University of Liverpool الأسماء السابقة كلية ليفربول الجامعية (1882-1884) جامعة فيكتوريا في ليفربول (1884-1903) معلومات التأسيس 1882 (منذ 137 سنة) الإنتماءات رابطة الجامعات الأوروبية مجموعة راسل جامعات القرميد الأحمر المنحة المالية 143.5 مليون £ النوع جامعة عامة الكليات 6 الموقع الجغرافي إحداثيات 53°24′22″N 2°58′01″W  /  53.406°N 2.967°W  / 53.406; -2.967   المدينة ليفربول المكان   إنجلترا البلد   المملكة المتحدة رقم الهاتف 7942000 151 (44+) إحصاءات الطلاب 17,405 (سنة 2008) عضوية مجموعة رسل [1] أورسيد [2]   طلاب الدراسات العليا 3,860 الموقع www.liverpool.ac.uk تعديل   جامعة ليفربول مبنى فكتوريا جامعة ليفربول (بالإنجليزية: The University of Liverpool )) إحدى الجامعات البريطانية العريقة، تقع في مدينة ليفربول على الساحل الشمالي الغربي من أنجلترا . وهي عضو في مجموعة راسل للجامعات وتعتبر من ضمن جامعات الطوب الأحمر الستة. محتويات ...
                    Read more