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.
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!
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 ...
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)$?
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 \$...