Time complexity of a language whose alphabet has a single symbol
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Consider a language $L$ such that $L subseteq Sigma^*$, where the cardinality of $Sigma$ is $1$ (i.e. the alphabet has only one symbol). E.g. $L subseteq a^*$.
Can anything be said about the time complexity of $L$? Is it the case that $L in P$?
I can't come up with any example of a language with a single symbol that is not in $P$.
time-complexity decision-problem
asked 5 hours ago
denidare
182
add a comment |Â
up vote
2
down vote
favorite
Consider a language $L$ such that $L subseteq Sigma^*$, where the cardinality of $Sigma$ is $1$ (i.e. the alphabet has only one symbol). E.g. $L subseteq a^*$.
Can anything be said about the time complexity of $L$? Is it the case that $L in P$?
I can't come up with any example of a language with a single symbol that is not in $P$.
time-complexity decision-problem
asked 5 hours ago
denidare
182
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Consider a language $L$ such that $L subseteq Sigma^*$, where the cardinality of $Sigma$ is $1$ (i.e. the alphabet has only one symbol). E.g. $L subseteq a^*$.
Can anything be said about the time complexity of $L$? Is it the case that $L in P$?
I can't come up with any example of a language with a single symbol that is not in $P$.
time-complexity decision-problem
asked 5 hours ago
denidare
182
Consider a language $L$ such that $L subseteq Sigma^*$, where the cardinality of $Sigma$ is $1$ (i.e. the alphabet has only one symbol). E.g. $L subseteq a^*$.
Can anything be said about the time complexity of $L$? Is it the case that $L in P$?
I can't come up with any example of a language with a single symbol that is not in $P$.
time-complexity decision-problem
time-complexity decision-problem
asked 5 hours ago
denidare
182
asked 5 hours ago
denidare
182
asked 5 hours ago
denidare
182
asked 5 hours ago
denidare
182
asked 5 hours ago
denidare
182
182
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
The language $a^n : text the $n$th Turing machine halts on the empty string $ is undecidable.
In fact, a random unary language is undecidable almost surely, for the simple reason that there are only countably many computable languages.
answered 5 hours ago
Yuval Filmus
185k12176337
Thanks, this makes sense. Would anything change if we restricted $L$ to be decidable?
– denidare
5 hours ago
Perhaps you can search a bit on the Internet. You might find things like "if there exists a unary language that is NP-complete, then P = NP" and other interesting observations.
– Pål GD
4 hours ago
1
Not really. You can ask whether the $n$th Turing machine halts within $T(n)$ steps on the empty string, which should be hard to determine given much less than $T(n)$ time.
– Yuval Filmus
4 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
The language $a^n : text the $n$th Turing machine halts on the empty string $ is undecidable.
In fact, a random unary language is undecidable almost surely, for the simple reason that there are only countably many computable languages.
answered 5 hours ago
Yuval Filmus
185k12176337
Thanks, this makes sense. Would anything change if we restricted $L$ to be decidable?
– denidare
5 hours ago
Perhaps you can search a bit on the Internet. You might find things like "if there exists a unary language that is NP-complete, then P = NP" and other interesting observations.
– Pål GD
4 hours ago
1
Not really. You can ask whether the $n$th Turing machine halts within $T(n)$ steps on the empty string, which should be hard to determine given much less than $T(n)$ time.
– Yuval Filmus
4 hours ago
add a comment |Â
up vote
3
down vote
The language $a^n : text the $n$th Turing machine halts on the empty string $ is undecidable.
In fact, a random unary language is undecidable almost surely, for the simple reason that there are only countably many computable languages.
answered 5 hours ago
Yuval Filmus
185k12176337
Thanks, this makes sense. Would anything change if we restricted $L$ to be decidable?
– denidare
5 hours ago
Perhaps you can search a bit on the Internet. You might find things like "if there exists a unary language that is NP-complete, then P = NP" and other interesting observations.
– Pål GD
4 hours ago
1
Not really. You can ask whether the $n$th Turing machine halts within $T(n)$ steps on the empty string, which should be hard to determine given much less than $T(n)$ time.
– Yuval Filmus
4 hours ago
add a comment |Â
up vote
3
down vote
up vote
3
down vote
The language $a^n : text the $n$th Turing machine halts on the empty string $ is undecidable.
In fact, a random unary language is undecidable almost surely, for the simple reason that there are only countably many computable languages.
answered 5 hours ago
Yuval Filmus
185k12176337
The language $a^n : text the $n$th Turing machine halts on the empty string $ is undecidable.
In fact, a random unary language is undecidable almost surely, for the simple reason that there are only countably many computable languages.
answered 5 hours ago
Yuval Filmus
185k12176337
answered 5 hours ago
Yuval Filmus
185k12176337
answered 5 hours ago
Yuval Filmus
185k12176337
answered 5 hours ago
Yuval Filmus
185k12176337
185k12176337
Thanks, this makes sense. Would anything change if we restricted $L$ to be decidable?
– denidare
5 hours ago
Perhaps you can search a bit on the Internet. You might find things like "if there exists a unary language that is NP-complete, then P = NP" and other interesting observations.
– Pål GD
4 hours ago
1
Not really. You can ask whether the $n$th Turing machine halts within $T(n)$ steps on the empty string, which should be hard to determine given much less than $T(n)$ time.
– Yuval Filmus
4 hours ago
add a comment |Â
Thanks, this makes sense. Would anything change if we restricted $L$ to be decidable?
– denidare
5 hours ago
Perhaps you can search a bit on the Internet. You might find things like "if there exists a unary language that is NP-complete, then P = NP" and other interesting observations.
– Pål GD
4 hours ago
1
Not really. You can ask whether the $n$th Turing machine halts within $T(n)$ steps on the empty string, which should be hard to determine given much less than $T(n)$ time.
– Yuval Filmus
4 hours ago
Thanks, this makes sense. Would anything change if we restricted $L$ to be decidable?
– denidare
5 hours ago
Thanks, this makes sense. Would anything change if we restricted $L$ to be decidable?
– denidare
5 hours ago
Perhaps you can search a bit on the Internet. You might find things like "if there exists a unary language that is NP-complete, then P = NP" and other interesting observations.
– Pål GD
4 hours ago
Perhaps you can search a bit on the Internet. You might find things like "if there exists a unary language that is NP-complete, then P = NP" and other interesting observations.
– Pål GD
4 hours ago
1
1
Not really. You can ask whether the $n$th Turing machine halts within $T(n)$ steps on the empty string, which should be hard to determine given much less than $T(n)$ time.
– Yuval Filmus
4 hours ago
Not really. You can ask whether the $n$th Turing machine halts within $T(n)$ steps on the empty string, which should be hard to determine given much less than $T(n)$ time.
– Yuval Filmus
4 hours ago
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f99454%2ftime-complexity-of-a-language-whose-alphabet-has-a-single-symbol%23new-answer', 'question_page');
);
Post as a guest
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
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
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