Linked Questions
18 questions linked to/from Are there subexponential-time algorithms for NP-complete problems?
0
votes
1answer
87 views
is this time complexity subexponential? [duplicate]
Is next time complexity sub-exponential?
$O(2^{N^{LOG2(1.5)}}/8)$
unformatted: O((2^N)^LOG2(1.5))/8) just in case I didn't format it properly.
0
votes
0answers
75 views
Subexponential algorithm for Np-complete problems [duplicate]
https://cstheory.stackexchange.com/a/3627/32204
Could someone explain to me why this reasoning is false. I don't understand it! To me this sounds plausible!
0
votes
0answers
23 views
Assuming the Exponential Time Hypothesis is true, what's the fastest possible algorithm that can be produced for NP-complete problems? [duplicate]
Assuming the Exponential time hypothesis is true, what's the fast possible algorithm that can be produced for NP-complete problems?
If 3-Sat takes exponential time, then could it be possible that ...
12
votes
1answer
2k views
Which NP-Complete problem has the fastest known algorithm?
In terms of worst-case asymptotic runtime, which NP-complete problem has the fastest-known (exact) algorithm and what is the algorithm? Is there something known that is faster than $O(n^2*2^n)$?
9
votes
3answers
5k views
Do any decision problems exist outside NP and NP-Hard?
This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard.
In order to be in NP, problems have to have a ...
6
votes
2answers
2k views
Give one example where it takes Non- deterministically exponential time to solve the problem?
I am a starter in complexity theory though I have fair knowledge in Turing machine. I know what it means to be non-deterministically polynomial time solvable but I am trying to understand where the ...
5
votes
1answer
742 views
Strongly NP-hard problems and Dynamic Programming
Dynamic Programming seems to result in good performance algorithms for Weakly NP-hard Problems. Two examples are Subset Sum Problem and 0-1 Knapsack Problem, both problems are solvable in pseudo-...
7
votes
1answer
893 views
Fastest known algorithm for $3$-$\mathrm{Partition}$ problem
$3$-$\mathrm{Partition}$ problem is $\mathsf{NP}$-Complete in a strong sense meaning there is no pseudo-polynomial time algorithm for it unless $\mathsf{P=NP}$. I am looking for the fastest known ...
2
votes
1answer
304 views
Why doesn't subset sum solution violate Exponential Time Hypothesis?
The quickest algorithm for solving subset sum currently is $2^{n/2}$ (via Wiki). Why doesn't this violate the Exponential Time Hypothesis which states that “there is no family of algorithms that can ...
3
votes
1answer
76 views
Proving that an equal partition does not exist
We are given a set of $n$ numbers and want to know whether it can be partitioned to two sets with an equal sum.
To prove that an equal partition exists, it is sufficient to show a partition.
What is ...
2
votes
2answers
100 views
Does 'subexponential algorithm' refer to input or number of bits used to represent input?
When an algorithm is said to be subexponential - does this refer to the input N or the number of bits used to represent N? Consider the following: trial division for integer factorization (i.e. try ...
2
votes
1answer
172 views
Does an algorithm with complexity $\Theta(2^\sqrt{n})$ to solve any NP problem count as “good” and practical as any other polynomial algorithm?
If the complexity of an arbitrary algorithm to solve any NP problem after analysis is $\Theta(2^\sqrt{n})$ then is this algorithm considered as "good" and practical algorithm?
I know that in ...
1
vote
1answer
196 views
On SUBEXP ⊆ P/poly
According to answers here Are there subexponential-time algorithms for NP-complete problems? $\mathsf{NP}$ complete problems can be in $DTIME[2^{n^{1/\alpha}}]$ for $\alpha>1$.
Now supposing $...
4
votes
2answers
117 views
Should we always think of problems higher in the polynomial hierarchy as harder than problems lower in the hierarchy?
This "research vignette" (whatever that is) claims that the polynomial hierarchy
classifies problems according to a natural notion of logical complexity, and is defined with an infinite number of ...
2
votes
1answer
91 views
Can we solve this problem more efficiently than trying all possible combinations
Here is the context of the problem I am struggling with.
I have a set of strings, for example:
...