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”?
$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 9 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 9 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 9 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 9 hours ago
Joel MillerJoel Miller
553
asked 9 hours ago
Joel MillerJoel Miller
553
asked 9 hours ago
Joel MillerJoel Miller
553
asked 9 hours ago
Joel MillerJoel Miller
553
asked 9 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 8 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 8 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 8 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 8 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 8 hours ago
D.W.♦D.W.
99.7k12121286
edited 4 hours ago
answered 8 hours ago
D.W.♦D.W.
99.7k12121286
answered 8 hours ago
D.W.♦D.W.
99.7k12121286
answered 8 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
