If lower bound of a problem is exponential then is it NP?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Assuming that we have a problem $p$ and we showed that the lower bound for solving $p$ is $mathcalOmega(2^n)$.
- can lower bound $mathcalOmega(2^n)$ implies the problem in $NP$?
time-complexity np-complete
New contributor
add a comment |Â
up vote
2
down vote
favorite
Assuming that we have a problem $p$ and we showed that the lower bound for solving $p$ is $mathcalOmega(2^n)$.
- can lower bound $mathcalOmega(2^n)$ implies the problem in $NP$?
time-complexity np-complete
New contributor
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Assuming that we have a problem $p$ and we showed that the lower bound for solving $p$ is $mathcalOmega(2^n)$.
- can lower bound $mathcalOmega(2^n)$ implies the problem in $NP$?
time-complexity np-complete
New contributor
Assuming that we have a problem $p$ and we showed that the lower bound for solving $p$ is $mathcalOmega(2^n)$.
- can lower bound $mathcalOmega(2^n)$ implies the problem in $NP$?
time-complexity np-complete
time-complexity np-complete
New contributor
New contributor
New contributor
asked 16 mins ago
kelalaka
1135
1135
New contributor
New contributor
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
No. For example, the halting problem has an $Omega(2^n)$ lower bound, but it is not in NP (since it is not computable).
NP is an upper bound on the complexity of a problem.
do you know a computable example, also?
â kelalaka
11 mins ago
1
Yes. Take any NEXPTIME-complete problem.
â Yuval Filmus
10 mins ago
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
No. For example, the halting problem has an $Omega(2^n)$ lower bound, but it is not in NP (since it is not computable).
NP is an upper bound on the complexity of a problem.
do you know a computable example, also?
â kelalaka
11 mins ago
1
Yes. Take any NEXPTIME-complete problem.
â Yuval Filmus
10 mins ago
add a comment |Â
up vote
2
down vote
No. For example, the halting problem has an $Omega(2^n)$ lower bound, but it is not in NP (since it is not computable).
NP is an upper bound on the complexity of a problem.
do you know a computable example, also?
â kelalaka
11 mins ago
1
Yes. Take any NEXPTIME-complete problem.
â Yuval Filmus
10 mins ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
No. For example, the halting problem has an $Omega(2^n)$ lower bound, but it is not in NP (since it is not computable).
NP is an upper bound on the complexity of a problem.
No. For example, the halting problem has an $Omega(2^n)$ lower bound, but it is not in NP (since it is not computable).
NP is an upper bound on the complexity of a problem.
answered 12 mins ago
Yuval Filmus
183k12171333
183k12171333
do you know a computable example, also?
â kelalaka
11 mins ago
1
Yes. Take any NEXPTIME-complete problem.
â Yuval Filmus
10 mins ago
add a comment |Â
do you know a computable example, also?
â kelalaka
11 mins ago
1
Yes. Take any NEXPTIME-complete problem.
â Yuval Filmus
10 mins ago
do you know a computable example, also?
â kelalaka
11 mins ago
do you know a computable example, also?
â kelalaka
11 mins ago
1
1
Yes. Take any NEXPTIME-complete problem.
â Yuval Filmus
10 mins ago
Yes. Take any NEXPTIME-complete problem.
â Yuval Filmus
10 mins ago
add a comment |Â
kelalaka is a new contributor. Be nice, and check out our Code of Conduct.
kelalaka is a new contributor. Be nice, and check out our Code of Conduct.
kelalaka is a new contributor. Be nice, and check out our Code of Conduct.
kelalaka is a new contributor. Be nice, and check out our Code of Conduct.
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%2f98277%2fif-lower-bound-of-a-problem-is-exponential-then-is-it-np%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