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?
Mac no longer boots
Does the DOJ's declining to investigate the Trump-Zelensky call ruin the basis for impeachment?
Should I hang doors before or after drywall?
Has Boris Johnson ever referred to any of his opponents as "traitors"?
If I travelled back in time to invest in X company to make a fortune, roughly what is the probability that it would fail?
As an interviewer, how to conduct interviews with candidates you already know will be rejected?
Young adult short story book with one story where a woman finds a walrus suit and becomes a walrus
How to prove (A v B), (A → C), (B → D) therefore (C v D)
Tikz background color of node multilayer
Can I return my ability to cast Wish by using Glyph of warding?
How to catch creatures that can predict the next few minutes?
What's the difference between motherboard and chassis?
Using 4K Skyrim Textures when running 1920 x 1080 display resolution?
Why do personal finance apps focus on outgoings rather than income
What are some ways to season that don't rely on garlic and onions?
Can/should you swim in zero G?
Is it unethical to give a gift to my professor who might potentially write me a LOR?
C - Learning Linked Lists, Pointer Manipulation - Store some ints, print and free memory
Could Boris Johnson face criminal charges for illegally proroguing Parliament?
Colleague's grant application resembles my PhD thesis
Sum of series with addition
Can an NPC use the teleport spell to affect an object they can see with the scry spell?
How fast are we moving relative to the CMB?
Notation clarity question for a conglomerate of accidentals
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^sqrtn)$ (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^sqrtn)$ (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
11 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^sqrtn)$ (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^sqrtn)$ (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
11 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
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
$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
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
11 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-nl$ 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 9 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-nl$ 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 9 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-nl$ 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 9 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-nl$ 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 9 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-nl$ 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 9 mins ago
Mohsen GhorbaniMohsen Ghorbani
1722 silver badges9 bronze badges
edited 2 mins ago
answered 9 mins ago
Mohsen GhorbaniMohsen Ghorbani
1722 silver badges9 bronze badges
answered 9 mins ago
Mohsen GhorbaniMohsen Ghorbani
1722 silver badges9 bronze badges
answered 9 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
11 hours ago