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

                    SQL Server 17 - Attemping to backup to remote NAS but Access is denied

                    Image
                    .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0; } 0 I was attemping to use Ola Hallengrens scripts to backup to a remote NAS, but it was failing and not giving any direct errors, so I tried doing it manually using Server Management Studio and got the following error: TITLE: Microsoft SQL Server Management Studio Failed to retrieve data for this request. (Microsoft.SqlServer.Management.Sdk.Sfc) For help, click: http://go.microsoft.com/fwlink?ProdName=Microsoft%20SQL%20Server&LinkId=20476 ADDITIONAL INFORMATION: An exception occurred while executing a Transact-SQL statement or batch. (Microsoft.SqlServer.ConnectionInfo) The operating system returned the error '0x80070005(Access is denied.)&#
                    Read more

                    Always On Availability groups resolving state after failover - Remote harden of transaction...

                    Image
                    0 My explanation will be opinion based as it is based on my findings. If more information is needed, I am always happy to add it. The setup We have 4 SQL Server 2016 Instances, and all 4 underlying servers are in a WSFC (In my eyes a strange setup since Always On AG's are 2 by 2. But that is a different question.) 4 nodes + Fileshare witness Version: 13.0.5026.0 (all nodes) The instances that are having the failover issues are instances 1 & 2. They have 3 AG's between them. AG1 is primary on instance 1 and is having the issue. AG2 and AG3 are primary on instance 2. Instances 3 and 4 have their own separate AG's (2). AG1's settings The week before Last week, after checking for long running queries (none) and the synchronization state (green accross the board) we initiated a
                    Read more

                    Restoring from pg_dump with foreign key constraints

                    Image
                    5 2 In restoring a database from a pg_dump , a number of errors are being generated and the whole table is subsequently being ignored. An example: ERROR: insert or update on table "channelproducts" violates foreign key constraint "fk_rails_dfaae373a5" DETAIL: Key (channel_id)=(1) is not present in table "channels". Interestingly enough, I've noted that all these instances are popping up because of the sequence of loading. channels is after channelproducts both alphabetically and in the file and thus I can understand why postgres complains about having to create a child without a parent. caveat: the foreign key is being generated automatically by rails 4.2: I could remove the problem at the source but that still does not really solve the problem... version: PostgreSQL
                    Read more