New answers tagged np-hardness
1
vote
Running time of SAT and other EXPTIME algorithms
$O(n^2 \cdot 2^s) = O(2^{\log_2(n^2)} \cdot 2^s) = O(2^{s+2log_2(n)})$, so your provided runtime is still in $EXPTIME$ as long as $n \in 2^{O(\text{poly}(s))}$.
For your second question, I'm not ...
- 742
Top 50 recent answers are included