What's after EXPSPACE?
$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:
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.
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
asked 6 hours ago
Joel MillerJoel Miller
553
$endgroup$
add a comment |
$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:
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.
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
asked 6 hours ago
Joel MillerJoel Miller
553
$endgroup$
add a comment |
$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:
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.
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
asked 6 hours ago
Joel MillerJoel Miller
553
$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:
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.
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
complexity-theory computability decision-problem space-complexity
asked 6 hours ago
Joel MillerJoel Miller
553
asked 6 hours ago
Joel MillerJoel Miller
553
asked 6 hours ago
Joel MillerJoel Miller
553
asked 6 hours ago
Joel MillerJoel Miller
553
asked 6 hours ago
Joel MillerJoel Miller
553
553
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$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).
answered 5 hours ago
D.W.♦D.W.
99.7k12121286
$endgroup$
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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).
answered 5 hours ago
D.W.♦D.W.
99.7k12121286
$endgroup$
add a comment |
$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).
answered 5 hours ago
D.W.♦D.W.
99.7k12121286
$endgroup$
add a comment |
$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).
answered 5 hours ago
D.W.♦D.W.
99.7k12121286
$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).
answered 5 hours ago
D.W.♦D.W.
99.7k12121286
edited 1 hour ago
answered 5 hours ago
D.W.♦D.W.
99.7k12121286
answered 5 hours ago
D.W.♦D.W.
99.7k12121286
answered 5 hours ago
D.W.♦D.W.
99.7k12121286
99.7k12121286
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
