Are there any NP complete problems in SUB EXP TIME?A polynomial reduction from any NP-complete problem to...
SHA3-255, one bit less
Does it require less energy to reach the Sun from Pluto's orbit than from Earth's orbit?
Tikz background color of node multilayer
Does the US Armed Forces refuse to recruit anyone with an IQ less than 83?
"cd" into /sys/kernel/debug/tracing causes permission change
Redirect output on-the-fly - looks not possible in Linux, why?
Bothered by watching coworkers slacking off
Advices to added homemade symbols
Would houseruling two or more instances of resistance to the same element as immunity be overly unbalanced?
Is there any problem with students seeing faculty naked in university gym?
Driving test in New Zealand?
What's the difference between motherboard and chassis?
Did Joe Biden "stop a prosecution" into his son in Ukraine? And did he brag about stopping the prosecution?
How fast are we moving relative to the CMB?
Can 35 mm film which went through a washing machine still be developed?
"last" command not working properly
What are some ways to season that don't rely on garlic and onions?
Search for something difficult to count/estimate
Is right click on tables bad UX
How is the speed of nucleons in the nucleus measured?
What’s the BrE for “shotgun wedding”?
Why is the time of useful consciousness only seconds at high altitudes?
What does a textbook look like while you are writing it?
Manager told a colleague of mine I was getting fired soon
Are there any NP complete problems in SUB EXP TIME?
A polynomial reduction from any NP-complete problem to bounded PCPResource bounded reductions for RE-Complete problemsDo there exist “O(1)-complete” problems?Is there an NP-complete problem that can be solved in $O(n^{log n})$ time?Computationally 'hard' polynomial-time reduction to other NP-complete problems / Hierarchy of NP-complete problemsIs there any polynomial time algorithm for a restricted EXP-time problem?Problems that feel exponential but are PWhy is $ZPP geq BPP$ not true?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{
margin-bottom:0;
}
$begingroup$
Generally most np complete problems seem to have the best strategies operate in time $O(c^n$) for some choice of $c$
Has something like $O(2^sqrt{n})$ (or any other less than exponential but greater than polynomial running time) ever been encountered in the wild as a run time for an algorithm that solves an NP complete problem?
complexity-theory
asked 12 hours ago
frogeyedpeasfrogeyedpeas
1931 silver badge7 bronze badges
$endgroup$
add a comment
|
$begingroup$
Generally most np complete problems seem to have the best strategies operate in time $O(c^n$) for some choice of $c$
Has something like $O(2^sqrt{n})$ (or any other less than exponential but greater than polynomial running time) ever been encountered in the wild as a run time for an algorithm that solves an NP complete problem?
complexity-theory
asked 12 hours ago
frogeyedpeasfrogeyedpeas
1931 silver badge7 bronze badges
$endgroup$
$begingroup$
According to the ETH np-complete problems does not have $2^{o(n)}$ time complexity.
$endgroup$
– Mohsen Ghorbani
11 hours ago
1
$begingroup$
No, the ETH refers only to SAT, not to all NP-complete problems.
$endgroup$
– Hermann Gruber
11 hours ago
$begingroup$
Yes my bad... but I think there are not known np-complete solvable in $2^{o(n)}$, also padded version of SAT(or any npc) has the property you want.
$endgroup$
– Mohsen Ghorbani
10 hours ago
add a comment
|
$begingroup$
Generally most np complete problems seem to have the best strategies operate in time $O(c^n$) for some choice of $c$
Has something like $O(2^sqrt{n})$ (or any other less than exponential but greater than polynomial running time) ever been encountered in the wild as a run time for an algorithm that solves an NP complete problem?
complexity-theory
asked 12 hours ago
frogeyedpeasfrogeyedpeas
1931 silver badge7 bronze badges
$endgroup$
Generally most np complete problems seem to have the best strategies operate in time $O(c^n$) for some choice of $c$
Has something like $O(2^sqrt{n})$ (or any other less than exponential but greater than polynomial running time) ever been encountered in the wild as a run time for an algorithm that solves an NP complete problem?
complexity-theory
complexity-theory
asked 12 hours ago
frogeyedpeasfrogeyedpeas
1931 silver badge7 bronze badges
asked 12 hours ago
frogeyedpeasfrogeyedpeas
1931 silver badge7 bronze badges
asked 12 hours ago
frogeyedpeasfrogeyedpeas
1931 silver badge7 bronze badges
asked 12 hours ago
frogeyedpeasfrogeyedpeas
1931 silver badge7 bronze badges
asked 12 hours ago
frogeyedpeasfrogeyedpeas
1931 silver badge7 bronze badges
1931 silver badge7 bronze badges
$begingroup$
According to the ETH np-complete problems does not have $2^{o(n)}$ time complexity.
$endgroup$
– Mohsen Ghorbani
11 hours ago
1
$begingroup$
No, the ETH refers only to SAT, not to all NP-complete problems.
$endgroup$
– Hermann Gruber
11 hours ago
$begingroup$
Yes my bad... but I think there are not known np-complete solvable in $2^{o(n)}$, also padded version of SAT(or any npc) has the property you want.
$endgroup$
– Mohsen Ghorbani
10 hours ago
add a comment
|
$begingroup$
According to the ETH np-complete problems does not have $2^{o(n)}$ time complexity.
$endgroup$
– Mohsen Ghorbani
11 hours ago
1
$begingroup$
No, the ETH refers only to SAT, not to all NP-complete problems.
$endgroup$
– Hermann Gruber
11 hours ago
$begingroup$
Yes my bad... but I think there are not known np-complete solvable in $2^{o(n)}$, also padded version of SAT(or any npc) has the property you want.
$endgroup$
– Mohsen Ghorbani
10 hours ago
$begingroup$
According to the ETH np-complete problems does not have $2^{o(n)}$ time complexity.
$endgroup$
– Mohsen Ghorbani
11 hours ago
$begingroup$
According to the ETH np-complete problems does not have $2^{o(n)}$ time complexity.
$endgroup$
– Mohsen Ghorbani
11 hours ago
1
1
$begingroup$
No, the ETH refers only to SAT, not to all NP-complete problems.
$endgroup$
– Hermann Gruber
11 hours ago
$begingroup$
No, the ETH refers only to SAT, not to all NP-complete problems.
$endgroup$
– Hermann Gruber
11 hours ago
$begingroup$
Yes my bad... but I think there are not known np-complete solvable in $2^{o(n)}$, also padded version of SAT(or any npc) has the property you want.
$endgroup$
– Mohsen Ghorbani
10 hours ago
$begingroup$
Yes my bad... but I think there are not known np-complete solvable in $2^{o(n)}$, also padded version of SAT(or any npc) has the property you want.
$endgroup$
– Mohsen Ghorbani
10 hours ago
add a comment
|
2 Answers
2
active
oldest
votes
$begingroup$
The maximum clique problem on graphs with $m$ edges is solvable in time $2^{O(sqrt m)}$. See Lemma 11.6 in F. Fomin and D. Kratsch, exact exponential algorithms, Springer, 2010. Also, note that PLANAR 3-SAT, while NP-complete, is solvable in time $2^{O(sqrt n)}$, where $n$ denotes the number of vertices: https://cstheory.stackexchange.com/questions/30883/are-there-subexponential-algorithms-for-planar-sat-known
answered 11 hours ago
Hermann GruberHermann Gruber
1755 bronze badges
$endgroup$
add a comment
|
$begingroup$
Suppose there is a $O(2^n)$ time algorithm for set $L$ and $L in NP-complete$. define $L'={1^{n^c-n}l| lin L& |l|=n }$ it is easy to prove that $L' in NP-complete$ and there is a $O(2^{sqrt[c]{n}})$ time algorithm for $L'$. On the other hand according to ETH $SAT$ can't be solved in time $2^{o(n)}$ and it is enough to conclude that there are no $NP$-complete such that solvable in time $n^{poly(log n)}$. The best known algorithm for 3-SAT is in time $1.3^n$ or at least near this number.
answered 2 mins ago
Mohsen GhorbaniMohsen Ghorbani
1722 silver badges9 bronze badges
$endgroup$
add a comment
|
Your Answer
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/4.0/"u003ecc by-sa 4.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%2f115167%2fare-there-any-np-complete-problems-in-sub-exp-time%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The maximum clique problem on graphs with $m$ edges is solvable in time $2^{O(sqrt m)}$. See Lemma 11.6 in F. Fomin and D. Kratsch, exact exponential algorithms, Springer, 2010. Also, note that PLANAR 3-SAT, while NP-complete, is solvable in time $2^{O(sqrt n)}$, where $n$ denotes the number of vertices: https://cstheory.stackexchange.com/questions/30883/are-there-subexponential-algorithms-for-planar-sat-known
answered 11 hours ago
Hermann GruberHermann Gruber
1755 bronze badges
$endgroup$
add a comment
|
$begingroup$
The maximum clique problem on graphs with $m$ edges is solvable in time $2^{O(sqrt m)}$. See Lemma 11.6 in F. Fomin and D. Kratsch, exact exponential algorithms, Springer, 2010. Also, note that PLANAR 3-SAT, while NP-complete, is solvable in time $2^{O(sqrt n)}$, where $n$ denotes the number of vertices: https://cstheory.stackexchange.com/questions/30883/are-there-subexponential-algorithms-for-planar-sat-known
answered 11 hours ago
Hermann GruberHermann Gruber
1755 bronze badges
$endgroup$
add a comment
|
$begingroup$
The maximum clique problem on graphs with $m$ edges is solvable in time $2^{O(sqrt m)}$. See Lemma 11.6 in F. Fomin and D. Kratsch, exact exponential algorithms, Springer, 2010. Also, note that PLANAR 3-SAT, while NP-complete, is solvable in time $2^{O(sqrt n)}$, where $n$ denotes the number of vertices: https://cstheory.stackexchange.com/questions/30883/are-there-subexponential-algorithms-for-planar-sat-known
answered 11 hours ago
Hermann GruberHermann Gruber
1755 bronze badges
$endgroup$
The maximum clique problem on graphs with $m$ edges is solvable in time $2^{O(sqrt m)}$. See Lemma 11.6 in F. Fomin and D. Kratsch, exact exponential algorithms, Springer, 2010. Also, note that PLANAR 3-SAT, while NP-complete, is solvable in time $2^{O(sqrt n)}$, where $n$ denotes the number of vertices: https://cstheory.stackexchange.com/questions/30883/are-there-subexponential-algorithms-for-planar-sat-known
answered 11 hours ago
Hermann GruberHermann Gruber
1755 bronze badges
edited 7 hours ago
answered 11 hours ago
Hermann GruberHermann Gruber
1755 bronze badges
answered 11 hours ago
Hermann GruberHermann Gruber
1755 bronze badges
answered 11 hours ago
Hermann GruberHermann Gruber
1755 bronze badges
1755 bronze badges
add a comment
|
add a comment
|
$begingroup$
Suppose there is a $O(2^n)$ time algorithm for set $L$ and $L in NP-complete$. define $L'={1^{n^c-n}l| lin L& |l|=n }$ it is easy to prove that $L' in NP-complete$ and there is a $O(2^{sqrt[c]{n}})$ time algorithm for $L'$. On the other hand according to ETH $SAT$ can't be solved in time $2^{o(n)}$ and it is enough to conclude that there are no $NP$-complete such that solvable in time $n^{poly(log n)}$. The best known algorithm for 3-SAT is in time $1.3^n$ or at least near this number.
answered 2 mins ago
Mohsen GhorbaniMohsen Ghorbani
1722 silver badges9 bronze badges
$endgroup$
add a comment
|
$begingroup$
Suppose there is a $O(2^n)$ time algorithm for set $L$ and $L in NP-complete$. define $L'={1^{n^c-n}l| lin L& |l|=n }$ it is easy to prove that $L' in NP-complete$ and there is a $O(2^{sqrt[c]{n}})$ time algorithm for $L'$. On the other hand according to ETH $SAT$ can't be solved in time $2^{o(n)}$ and it is enough to conclude that there are no $NP$-complete such that solvable in time $n^{poly(log n)}$. The best known algorithm for 3-SAT is in time $1.3^n$ or at least near this number.
answered 2 mins ago
Mohsen GhorbaniMohsen Ghorbani
1722 silver badges9 bronze badges
$endgroup$
add a comment
|
$begingroup$
Suppose there is a $O(2^n)$ time algorithm for set $L$ and $L in NP-complete$. define $L'={1^{n^c-n}l| lin L& |l|=n }$ it is easy to prove that $L' in NP-complete$ and there is a $O(2^{sqrt[c]{n}})$ time algorithm for $L'$. On the other hand according to ETH $SAT$ can't be solved in time $2^{o(n)}$ and it is enough to conclude that there are no $NP$-complete such that solvable in time $n^{poly(log n)}$. The best known algorithm for 3-SAT is in time $1.3^n$ or at least near this number.
answered 2 mins ago
Mohsen GhorbaniMohsen Ghorbani
1722 silver badges9 bronze badges
$endgroup$
Suppose there is a $O(2^n)$ time algorithm for set $L$ and $L in NP-complete$. define $L'={1^{n^c-n}l| lin L& |l|=n }$ it is easy to prove that $L' in NP-complete$ and there is a $O(2^{sqrt[c]{n}})$ time algorithm for $L'$. On the other hand according to ETH $SAT$ can't be solved in time $2^{o(n)}$ and it is enough to conclude that there are no $NP$-complete such that solvable in time $n^{poly(log n)}$. The best known algorithm for 3-SAT is in time $1.3^n$ or at least near this number.
answered 2 mins ago
Mohsen GhorbaniMohsen Ghorbani
1722 silver badges9 bronze badges
answered 2 mins ago
Mohsen GhorbaniMohsen Ghorbani
1722 silver badges9 bronze badges
answered 2 mins ago
Mohsen GhorbaniMohsen Ghorbani
1722 silver badges9 bronze badges
answered 2 mins ago
Mohsen GhorbaniMohsen Ghorbani
1722 silver badges9 bronze badges
1722 silver badges9 bronze badges
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%2f115167%2fare-there-any-np-complete-problems-in-sub-exp-time%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
$begingroup$
According to the ETH np-complete problems does not have $2^{o(n)}$ time complexity.
$endgroup$
– Mohsen Ghorbani
11 hours ago
1
$begingroup$
No, the ETH refers only to SAT, not to all NP-complete problems.
$endgroup$
– Hermann Gruber
11 hours ago
$begingroup$
Yes my bad... but I think there are not known np-complete solvable in $2^{o(n)}$, also padded version of SAT(or any npc) has the property you want.
$endgroup$
– Mohsen Ghorbani
10 hours ago