Ordering on Time Complexity Classes
up vote
0
down vote
favorite
In Sipser, the time complexity class $mathrm{TIME}(f(n))$ with respect to a function $f colon mathbb{N} to mathbb{N}$ is defined to be the collection of all languages that are decidable by an $O(f(n))$ time Turing machine.
It is easy to give some examples of containment relations between complexity classes from this definition: $mathrm{TIME}(n) =mathrm{TIME}(2n)$ and $mathrm{TIME}(n) subseteq mathrm{TIME}(n^2)$.
Now I guess it is natural (?) to ask the following question: given any two such complexity-generating functions $f,g$, is it always the case that either $mathrm{TIME}(f(n)) subseteq mathrm{TIME}(g(n))$ or $mathrm{TIME}(f(n)) supseteq mathrm{TIME}(g(n))$? If the answer is yes (which would surprise me a little), this would define a total order on the space of functions $mathbb N^{mathbb N}$.
computational-complexity
asked 13 hours ago
P. Factor
31519
add a comment |
up vote
0
down vote
favorite
In Sipser, the time complexity class $mathrm{TIME}(f(n))$ with respect to a function $f colon mathbb{N} to mathbb{N}$ is defined to be the collection of all languages that are decidable by an $O(f(n))$ time Turing machine.
It is easy to give some examples of containment relations between complexity classes from this definition: $mathrm{TIME}(n) =mathrm{TIME}(2n)$ and $mathrm{TIME}(n) subseteq mathrm{TIME}(n^2)$.
Now I guess it is natural (?) to ask the following question: given any two such complexity-generating functions $f,g$, is it always the case that either $mathrm{TIME}(f(n)) subseteq mathrm{TIME}(g(n))$ or $mathrm{TIME}(f(n)) supseteq mathrm{TIME}(g(n))$? If the answer is yes (which would surprise me a little), this would define a total order on the space of functions $mathbb N^{mathbb N}$.
computational-complexity
asked 13 hours ago
P. Factor
31519
It's certainly possible to find monotonic functions $f, g$ such that neither $f = O(g)$ nor $g = O(f)$; for example, let $E(n)$ equal $1$ if $n$ is even and $0$ otherwise, and define $f(n) = 2^{2^{n+E(n)}}$ and $g(n) = 2^{2^{n + 1 - E(n)}}$. I don't know if there are languages in the corresponding complexity classes, though.
– Connor Harris
13 hours ago
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
In Sipser, the time complexity class $mathrm{TIME}(f(n))$ with respect to a function $f colon mathbb{N} to mathbb{N}$ is defined to be the collection of all languages that are decidable by an $O(f(n))$ time Turing machine.
It is easy to give some examples of containment relations between complexity classes from this definition: $mathrm{TIME}(n) =mathrm{TIME}(2n)$ and $mathrm{TIME}(n) subseteq mathrm{TIME}(n^2)$.
Now I guess it is natural (?) to ask the following question: given any two such complexity-generating functions $f,g$, is it always the case that either $mathrm{TIME}(f(n)) subseteq mathrm{TIME}(g(n))$ or $mathrm{TIME}(f(n)) supseteq mathrm{TIME}(g(n))$? If the answer is yes (which would surprise me a little), this would define a total order on the space of functions $mathbb N^{mathbb N}$.
computational-complexity
asked 13 hours ago
P. Factor
31519
In Sipser, the time complexity class $mathrm{TIME}(f(n))$ with respect to a function $f colon mathbb{N} to mathbb{N}$ is defined to be the collection of all languages that are decidable by an $O(f(n))$ time Turing machine.
It is easy to give some examples of containment relations between complexity classes from this definition: $mathrm{TIME}(n) =mathrm{TIME}(2n)$ and $mathrm{TIME}(n) subseteq mathrm{TIME}(n^2)$.
Now I guess it is natural (?) to ask the following question: given any two such complexity-generating functions $f,g$, is it always the case that either $mathrm{TIME}(f(n)) subseteq mathrm{TIME}(g(n))$ or $mathrm{TIME}(f(n)) supseteq mathrm{TIME}(g(n))$? If the answer is yes (which would surprise me a little), this would define a total order on the space of functions $mathbb N^{mathbb N}$.
computational-complexity
computational-complexity
asked 13 hours ago
P. Factor
31519
asked 13 hours ago
P. Factor
31519
asked 13 hours ago
P. Factor
31519
asked 13 hours ago
P. Factor
31519
asked 13 hours ago
P. Factor
31519
31519
It's certainly possible to find monotonic functions $f, g$ such that neither $f = O(g)$ nor $g = O(f)$; for example, let $E(n)$ equal $1$ if $n$ is even and $0$ otherwise, and define $f(n) = 2^{2^{n+E(n)}}$ and $g(n) = 2^{2^{n + 1 - E(n)}}$. I don't know if there are languages in the corresponding complexity classes, though.
– Connor Harris
13 hours ago
add a comment |
It's certainly possible to find monotonic functions $f, g$ such that neither $f = O(g)$ nor $g = O(f)$; for example, let $E(n)$ equal $1$ if $n$ is even and $0$ otherwise, and define $f(n) = 2^{2^{n+E(n)}}$ and $g(n) = 2^{2^{n + 1 - E(n)}}$. I don't know if there are languages in the corresponding complexity classes, though.
– Connor Harris
13 hours ago
It's certainly possible to find monotonic functions $f, g$ such that neither $f = O(g)$ nor $g = O(f)$; for example, let $E(n)$ equal $1$ if $n$ is even and $0$ otherwise, and define $f(n) = 2^{2^{n+E(n)}}$ and $g(n) = 2^{2^{n + 1 - E(n)}}$. I don't know if there are languages in the corresponding complexity classes, though.
– Connor Harris
13 hours ago
It's certainly possible to find monotonic functions $f, g$ such that neither $f = O(g)$ nor $g = O(f)$; for example, let $E(n)$ equal $1$ if $n$ is even and $0$ otherwise, and define $f(n) = 2^{2^{n+E(n)}}$ and $g(n) = 2^{2^{n + 1 - E(n)}}$. I don't know if there are languages in the corresponding complexity classes, though.
– Connor Harris
13 hours ago
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2fmath.stackexchange.com%2fquestions%2f3006701%2fordering-on-time-complexity-classes%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
It's certainly possible to find monotonic functions $f, g$ such that neither $f = O(g)$ nor $g = O(f)$; for example, let $E(n)$ equal $1$ if $n$ is even and $0$ otherwise, and define $f(n) = 2^{2^{n+E(n)}}$ and $g(n) = 2^{2^{n + 1 - E(n)}}$. I don't know if there are languages in the corresponding complexity classes, though.
– Connor Harris
13 hours ago