What's after EXPSPACE?Do non-computable functions grow asymptotically larger?complexity of decision problems...

Is there a file that always exists and a 'normal' user can't lstat it?

Count repetitions of an array

Has any human ever had the choice to leave Earth permanently?

How do you funnel food off a cutting board?

What is the difference between "...", '...', $'...', and $"..." quotes?

Small Stakes NLH 1-2 $300 Cap - What did villain have?

Converting very wide logos to square formats

Custom shape shows unwanted extra line

Potential client has a problematic employee I can't work with

In harmony: key or the flow?

When obtaining gender reassignment/plastic surgery overseas, is an emergency travel document required to return home?

What's the oldest plausible frozen specimen for a Jurassic Park style story-line?

"Starve to death" Vs. "Starve to the point of death"

Calculate of total length of edges in Voronoi diagram

How big is a framed opening for a door relative to the finished door opening width?

Why do all the books in Game of Thrones library have their covers facing the back of the shelf?

Is there a way to not have to poll the UART of an AVR?

The No-Straight Maze

Square Root Distance from Integers

Microtypography protrusion with Polish quotation marks

Renting a 2CV in France

Why didn't Tom Riddle take the presence of Fawkes and the Sorting Hat as more of a threat?

How does Leonard in "Memento" remember reading and writing?

Categorical Unification of Jordan Holder Theorems



What's after EXPSPACE?


Do non-computable functions grow asymptotically larger?complexity of decision problems vs computing functionsP, NP and specialised Turing MachinesDoes converting algorithms into elementary recursive form preserve runtime bounds?Relation of Space and Time in Complexity?Complexity Classes (P, NP) vs Language Hierarchies (REC, RE)Turing reductions by NX ∩ coNX and binary relation problemsWhat is the big-O (worst-case upper bound) for time and space requirement of the different Chomsky classes?What is the complexity class of solving hash decision problems?Is there some problem in “promise-DSPACE(o(log log n))” that is also in “promise-DFA”?













4












$begingroup$


As far as I'm aware, EXPSPACE is the most inclusive computational complexity class. I was wondering if/how people conceptualize supersets of EXPSPACE.



Thinking about this question, I came up with a couple thoughts of my own:




  1. Maybe EXPSPACE = the set of all Recursively Enumerable problems, i.e. $Delta_1$ in the arithmetical hierarchy. In this case, the rest of the arithmetical hierarchy would come after EXPSPACE.


  2. Maybe there are problems with space requirements that need to be described by non-computatable functions. For example, take the Busy Beaver function, $BB(n)$, which returns the maximum number of steps an $n$-state Turing Machine could take before halting. $BB$ grows faster than any computable function -- so if a problem required $BB(n)$ space to solve, maybe that would put it in a complexity class after EXPSPACE? In other words, maybe after EXPSPACE there is one or more sets of problems that require a non-computable amount of space to solve.











share|cite|improve this question









$endgroup$

















    4












    $begingroup$


    As far as I'm aware, EXPSPACE is the most inclusive computational complexity class. I was wondering if/how people conceptualize supersets of EXPSPACE.



    Thinking about this question, I came up with a couple thoughts of my own:




    1. Maybe EXPSPACE = the set of all Recursively Enumerable problems, i.e. $Delta_1$ in the arithmetical hierarchy. In this case, the rest of the arithmetical hierarchy would come after EXPSPACE.


    2. Maybe there are problems with space requirements that need to be described by non-computatable functions. For example, take the Busy Beaver function, $BB(n)$, which returns the maximum number of steps an $n$-state Turing Machine could take before halting. $BB$ grows faster than any computable function -- so if a problem required $BB(n)$ space to solve, maybe that would put it in a complexity class after EXPSPACE? In other words, maybe after EXPSPACE there is one or more sets of problems that require a non-computable amount of space to solve.











    share|cite|improve this question









    $endgroup$















      4












      4








      4





      $begingroup$


      As far as I'm aware, EXPSPACE is the most inclusive computational complexity class. I was wondering if/how people conceptualize supersets of EXPSPACE.



      Thinking about this question, I came up with a couple thoughts of my own:




      1. Maybe EXPSPACE = the set of all Recursively Enumerable problems, i.e. $Delta_1$ in the arithmetical hierarchy. In this case, the rest of the arithmetical hierarchy would come after EXPSPACE.


      2. Maybe there are problems with space requirements that need to be described by non-computatable functions. For example, take the Busy Beaver function, $BB(n)$, which returns the maximum number of steps an $n$-state Turing Machine could take before halting. $BB$ grows faster than any computable function -- so if a problem required $BB(n)$ space to solve, maybe that would put it in a complexity class after EXPSPACE? In other words, maybe after EXPSPACE there is one or more sets of problems that require a non-computable amount of space to solve.











      share|cite|improve this question









      $endgroup$




      As far as I'm aware, EXPSPACE is the most inclusive computational complexity class. I was wondering if/how people conceptualize supersets of EXPSPACE.



      Thinking about this question, I came up with a couple thoughts of my own:




      1. Maybe EXPSPACE = the set of all Recursively Enumerable problems, i.e. $Delta_1$ in the arithmetical hierarchy. In this case, the rest of the arithmetical hierarchy would come after EXPSPACE.


      2. Maybe there are problems with space requirements that need to be described by non-computatable functions. For example, take the Busy Beaver function, $BB(n)$, which returns the maximum number of steps an $n$-state Turing Machine could take before halting. $BB$ grows faster than any computable function -- so if a problem required $BB(n)$ space to solve, maybe that would put it in a complexity class after EXPSPACE? In other words, maybe after EXPSPACE there is one or more sets of problems that require a non-computable amount of space to solve.








      complexity-theory computability decision-problem space-complexity






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked 9 hours ago









      Joel MillerJoel Miller

      553




      553






















          1 Answer
          1






          active

          oldest

          votes


















          4












          $begingroup$

          EXPSPACE is not the most inclusive computational complexity class. There's a huge number of complexity classes; see, e.g., the Complexity Zoo for some that have been studied (and in principle there are an unlimited number one could define).



          The space hierarchy theorem shows that for each $f(n)$, there are languages that can be decided in space $f(n)$ but cannot be decided in space $o(f(n))$. If we take $f(n)=2^{2^n}$ (say), then we find there are problems that can be decided in space $2^{2^n}$, but not in space $2^n$, and indeed, are not in EXPSPACE. So, we can "make up" a complexity class, call it 2EXPSPACE, of problems that can be solved in doubly-exponential space; it follows that 2EXPSPACE is bigger than EXPSPACE. And so on. There is an infinite hierarchy of complexity classes, each bigger than the previous.



          This also shows that EXPSPACE is not equal to RE (the recursively enumerable problems).






          share|cite|improve this answer











          $endgroup$













            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: "419"
            };
            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: false,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            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
            },
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f104835%2fwhats-after-expspace%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            4












            $begingroup$

            EXPSPACE is not the most inclusive computational complexity class. There's a huge number of complexity classes; see, e.g., the Complexity Zoo for some that have been studied (and in principle there are an unlimited number one could define).



            The space hierarchy theorem shows that for each $f(n)$, there are languages that can be decided in space $f(n)$ but cannot be decided in space $o(f(n))$. If we take $f(n)=2^{2^n}$ (say), then we find there are problems that can be decided in space $2^{2^n}$, but not in space $2^n$, and indeed, are not in EXPSPACE. So, we can "make up" a complexity class, call it 2EXPSPACE, of problems that can be solved in doubly-exponential space; it follows that 2EXPSPACE is bigger than EXPSPACE. And so on. There is an infinite hierarchy of complexity classes, each bigger than the previous.



            This also shows that EXPSPACE is not equal to RE (the recursively enumerable problems).






            share|cite|improve this answer











            $endgroup$


















              4












              $begingroup$

              EXPSPACE is not the most inclusive computational complexity class. There's a huge number of complexity classes; see, e.g., the Complexity Zoo for some that have been studied (and in principle there are an unlimited number one could define).



              The space hierarchy theorem shows that for each $f(n)$, there are languages that can be decided in space $f(n)$ but cannot be decided in space $o(f(n))$. If we take $f(n)=2^{2^n}$ (say), then we find there are problems that can be decided in space $2^{2^n}$, but not in space $2^n$, and indeed, are not in EXPSPACE. So, we can "make up" a complexity class, call it 2EXPSPACE, of problems that can be solved in doubly-exponential space; it follows that 2EXPSPACE is bigger than EXPSPACE. And so on. There is an infinite hierarchy of complexity classes, each bigger than the previous.



              This also shows that EXPSPACE is not equal to RE (the recursively enumerable problems).






              share|cite|improve this answer











              $endgroup$
















                4












                4








                4





                $begingroup$

                EXPSPACE is not the most inclusive computational complexity class. There's a huge number of complexity classes; see, e.g., the Complexity Zoo for some that have been studied (and in principle there are an unlimited number one could define).



                The space hierarchy theorem shows that for each $f(n)$, there are languages that can be decided in space $f(n)$ but cannot be decided in space $o(f(n))$. If we take $f(n)=2^{2^n}$ (say), then we find there are problems that can be decided in space $2^{2^n}$, but not in space $2^n$, and indeed, are not in EXPSPACE. So, we can "make up" a complexity class, call it 2EXPSPACE, of problems that can be solved in doubly-exponential space; it follows that 2EXPSPACE is bigger than EXPSPACE. And so on. There is an infinite hierarchy of complexity classes, each bigger than the previous.



                This also shows that EXPSPACE is not equal to RE (the recursively enumerable problems).






                share|cite|improve this answer











                $endgroup$



                EXPSPACE is not the most inclusive computational complexity class. There's a huge number of complexity classes; see, e.g., the Complexity Zoo for some that have been studied (and in principle there are an unlimited number one could define).



                The space hierarchy theorem shows that for each $f(n)$, there are languages that can be decided in space $f(n)$ but cannot be decided in space $o(f(n))$. If we take $f(n)=2^{2^n}$ (say), then we find there are problems that can be decided in space $2^{2^n}$, but not in space $2^n$, and indeed, are not in EXPSPACE. So, we can "make up" a complexity class, call it 2EXPSPACE, of problems that can be solved in doubly-exponential space; it follows that 2EXPSPACE is bigger than EXPSPACE. And so on. There is an infinite hierarchy of complexity classes, each bigger than the previous.



                This also shows that EXPSPACE is not equal to RE (the recursively enumerable problems).







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited 4 hours ago

























                answered 8 hours ago









                D.W.D.W.

                99.7k12121286




                99.7k12121286






























                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Computer Science Stack Exchange!


                    • 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%2fcs.stackexchange.com%2fquestions%2f104835%2fwhats-after-expspace%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

                    VNC viewer RFB protocol error: bad desktop size 0x0I Cannot Type the Key 'd' (lowercase) in VNC Viewer...

                    Couldn't open a raw socket. Error: Permission denied (13) (nmap)Is it possible to run networking commands...

                    Why not use the yoke to control yaw, as well as pitch and roll? Announcing the arrival of...