<p>Exact algorithms for NP-complete problems are sometimes feasible, if the input is small enough.</p>

<p>I’ve also came across some algorithms which are not practical even for very small inputs, and their importance is questionable.</p>

<p>I’m wondering what's the "hardest" (time complexity-wise) problems people have worked on its exact solution:</p>

<ol>
<li>The problem is in NP.</li>
<li>A non-trivial exact algorithm is known for the problem (preferably from the last few years).</li>
<li>No better algorithm is known.</li>
</ol>

<p>For example, the <a href="http://www.mif.vu.lt/~valdas/ALGORITMAI/Uzduotys2013/30%20%28DOMINATING%20SET%29/Fernau10.pdf" rel="nofollow">minimum dominating set of queens</a> has an algorithm which runs in $O(39.51^n\cdot poly(n))$ time.</p>

CC BY-SA 3.0
2014-01-19T19:18:16.803Z
Somehow, many fixed-parameterized algorithms fall into this category. For example: http://doi.org/10.1145/1411509.1411511; http://doi.org/10.1145/1993636.1993699
Yixin Cao
CC BY-SA 3.0
2014-01-19T20:31:01.947Z
having trouble following how these criteria would distinguish any NP complete problem from any other. it seems many/most NP complete problems can be solved exactly for small inputs. also, the listed criteria dont match the intro, no mention of small inputs is given in the listed criteria, is that an omission? and, all problems have a "nontrivial exact algorithm". as far as the theory is concerned, there seem to be few ways to discriminate any particular NP complete problem from any other... and there is the still-open "isomorphism conjecture" that in some deep senses they are "alike"...
vzn
CC BY-SA 3.0
2014-01-19T20:52:41.617Z
@vzn We definitely don't know if all problems have a non-trivial exact algorithm. In fact, for some problems, the fastest algorithm we known is exactly the trivial brute-force algorithm. As for the OP's question: typically fast non-trivial algorithms are known for local problems. So most probably the examples you are looking for are algorithms for non-local problems.
Juho
CC BY-SA 3.0
2014-01-19T21:33:40.973Z
@Juho This dichotomy is not only observed in NP-hard problems.  For example, there is only trivial algorithms for detecting a triangle, but there is very complicated algorithm for find the maximum matching.
Yixin Cao
CC BY-SA 3.0
2014-01-19T21:40:21.057Z
@YixinCao I guess the fastest you can do for triangle detection on $n$-vertex graphs is $O(n^\omega)$, where $\omega$ is the matrix multiplication constant. But no doubt you are right, I don't see why it should only be observed on NPC problems.
Juho
CC BY-SA 3.0
2014-01-19T21:41:31.347Z
@YixinCao,@Juho there is actually quite a nice, non-trivial algorithm for finding triangle in a graph (considerably faster than the trivial $n^3$ or $n^\omega$). See [here](http://www.tau.ac.il/~nogaa/PDFS/ayz4.pdf).
R B
CC BY-SA 3.0
2014-01-19T22:19:32.820Z
@Juho I consider the $O(n^{\omega}$-time algorithm trivial.  RB: That algorithm is very very nice, but is not better than the trivial ones in general.  Anyway, this comments seems off-topic.
Yixin Cao
CC BY-SA 3.0
2014-01-19T23:59:37.563Z
by "nontrivial" I mean an algorithm that may be brute force at heart but has minor enhancements. do not know of any NP complete problems that dont allow at least minor enhancements over brute force. has anyone given any example? even the example cited by the poster of dominating queens seems to be the opposite of what is asked for— it says there are good enhancements on the problem & details them. so what is a single good example of an NP complete problem that has no enhancements over brute force?
vzn
CC BY-SA 3.0
2014-01-20T04:02:38.440Z
@vzn, How do you define "minor enhancement"? $k$-SAT, which is virtually impossible to improve upon assuming SETH, seems to be a candidate? More directly, the problem of identifying if there exists a string *x* such that TM $A$ accepts input $x$ in $\leq |<A>|^k$ steps seems like an unlikely candidate for even minor enhancements.
Yonatan N
CC BY-SA 3.0
2014-01-20T06:43:29.483Z
@vzn, I think you misunderstood my intention.

I'm not looking for NP-hard questions with no better algorithm than the trivial.

I'm looking for questions (NP-complete or not) which people have devised a complex exact algorithm for, even though it's run time is not practical even for very short inputs.
R B
CC BY-SA 3.0
2014-01-20T06:46:48.903Z
@YixinCao - Can you please explain what you mean by "but is not better than the trivial ones in general"?

The algorithm finds triangle in time $O(|E|^{1.408})$ which is clearly better than $O(|V|^\omega)$ for any graph.
R B
CC BY-SA 3.0
2014-01-20T10:27:10.130Z
I really cannot understand what's a usage of this question in cstheory. Would you explain it? By the way, if you looking for problem which has a very big running time, may be is not bad to look at [maximum parsimony](http://en.wikipedia.org/wiki/Maximum_parsimony_%28phylogenetics%29) problem which inspired in bioinformatic. As I know, best known exact algorithm for this is bigger than n!!.
Saeed
CC BY-SA 3.0
2014-01-20T12:54:15.983Z
@Saeed - I'm trying to understand how much interest people have in exact algorithms which seems impractical.

If someone spent time constructing a non-trivial algorithm with runtime n!! I find it interesting, and I'm trying to understand how much research is done on such problems.
R B
CC BY-SA 3.0
2014-01-20T15:17:54.797Z
ok. re your last clarification think you are looking for something along lines of what RJLipton calls [galactic algorithms](http://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/) ie basically they have significant research value but are [currently] not used in practice [ie not implemented in running code] due to impracticality. see also [powerful algorithms too complex to implement](http://cstheory.stackexchange.com/questions/4491/powerful-algorithms-too-complex-to-implement)
vzn
CC BY-SA 3.0
2014-01-20T16:19:46.727Z
at this pt think the question phrasing is not clear and does not match clarifications by questioner in comments as also reflected by responses & further questions from multiple commenters. the 1-3 criteria listed apparently dont completely capture what questioner is looking for. there is no ref to "impractical for small inputs" in the 1-3 item criteria but RB repeats it in comments. at this pt it might be better to start out from scratch with new carefully rephrased question also maybe after questioner reviews the apparently related links & figures out if they are sufficient or not.
vzn
<ds.algorithms><reference-request><np-hardness><exp-time-algorithms><examples>
What's the hardest problem with a non-trivial exact algorithm?
R B
# What's the hardest problem with a non-trivial exact algorithm?

(Asked by: username_0 on 2014-01-18)

Exact algorithms for NP-complete problems are sometimes feasible, if the input is small enough.

I’ve also came across some algorithms which are not practical even for very small inputs, and their importance is questionable.

I’m wondering what's the "hardest" (time complexity-wise) problems people have worked on its exact solution:

1. The problem is in NP.
2. A non-trivial exact algorithm is known for the problem (preferably from the last few years).
3. No better algorithm is known.

For example, the [minimum dominating set of queens](http://www.mif.vu.lt/~valdas/ALGORITMAI/Uzduotys2013/30%20%28DOMINATING%20SET%29/Fernau10.pdf) has an algorithm which runs in $O(39.51^n\cdot poly(n))$ time.

**Tags:** ds.algorithms, reference-request, np-hardness, exp-time-algorithms, examples

> **Comments:**
> **username_1**: Somehow, many fixed-parameterized algorithms fall into this category. For example: http://doi.org/10.1145/1411509.1411511; http://doi.org/10.1145/1993636.1993699  
> **username_2**: having trouble following how these criteria would distinguish any NP complete problem from any other. it seems many/most NP complete problems can be solved exactly for small inputs. also, the listed criteria dont match the intro, no mention of small inputs is given in the listed criteria, is that an omission? and, all problems have a "nontrivial exact algorithm". as far as the theory is concerned, there seem to be few ways to discriminate any particular NP complete problem from any other... and there is the still-open "isomorphism conjecture" that in some deep senses they are "alike"...  
> **username_3**: @username_2 We definitely don't know if all problems have a non-trivial exact algorithm. In fact, for some problems, the fastest algorithm we known is exactly the trivial brute-force algorithm. As for the OP's question: typically fast non-trivial algorithms are known for local problems. So most probably the examples you are looking for are algorithms for non-local problems.  
> **username_1**: @username_3 This dichotomy is not only observed in NP-hard problems.  For example, there is only trivial algorithms for detecting a triangle, but there is very complicated algorithm for find the maximum matching.  
> **username_3**: @YixinCao I guess the fastest you can do for triangle detection on $n$-vertex graphs is $O(n^\omega)$, where $\omega$ is the matrix multiplication constant. But no doubt you are right, I don't see why it should only be observed on NPC problems.  
> **username_0**: @YixinCao,@username_3 there is actually quite a nice, non-trivial algorithm for finding triangle in a graph (considerably faster than the trivial $n^3$ or $n^\omega$). See [here](http://www.tau.ac.il/~nogaa/PDFS/ayz4.pdf).  
> **username_1**: @username_3 I consider the $O(n^{\omega}$-time algorithm trivial.  RB: That algorithm is very very nice, but is not better than the trivial ones in general.  Anyway, this comments seems off-topic.  
> **username_2**: by "nontrivial" I mean an algorithm that may be brute force at heart but has minor enhancements. do not know of any NP complete problems that dont allow at least minor enhancements over brute force. has anyone given any example? even the example cited by the poster of dominating queens seems to be the opposite of what is asked for— it says there are good enhancements on the problem & details them. so what is a single good example of an NP complete problem that has no enhancements over brute force?  
> **username_4**: @username_2, How do you define "minor enhancement"? $k$-SAT, which is virtually impossible to improve upon assuming SETH, seems to be a candidate? More directly, the problem of identifying if there exists a string *x* such that TM $A$ accepts input $x$ in $\leq |<A>|^k$ steps seems like an unlikely candidate for even minor enhancements.  
> **username_0**: @username_2, I think you misunderstood my intention.  I'm not looking for NP-hard questions with no better algorithm than the trivial.  I'm looking for questions (NP-complete or not) which people have devised a complex exact algorithm for, even though it's run time is not practical even for very short inputs.  
> **username_0**: @YixinCao - Can you please explain what you mean by "but is not better than the trivial ones in general"?  The algorithm finds triangle in time $O(|E|^{1.408})$ which is clearly better than $O(|V|^\omega)$ for any graph.  
> **username_5**: I really cannot understand what's a usage of this question in cstheory. Would you explain it? By the way, if you looking for problem which has a very big running time, may be is not bad to look at [maximum parsimony](http://en.wikipedia.org/wiki/Maximum_parsimony_%28phylogenetics%29) problem which inspired in bioinformatic. As I know, best known exact algorithm for this is bigger than n!!.  
> **username_0**: @username_5 - I'm trying to understand how much interest people have in exact algorithms which seems impractical.  If someone spent time constructing a non-trivial algorithm with runtime n!! I find it interesting, and I'm trying to understand how much research is done on such problems.  
> **username_2**: ok. re your last clarification think you are looking for something along lines of what RJLipton calls [galactic algorithms](http://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/) ie basically they have significant research value but are [currently] not used in practice [ie not implemented in running code] due to impracticality. see also [powerful algorithms too complex to implement](http://cstheory.stackexchange.com/questions/4491/powerful-algorithms-too-complex-to-implement)  
> **username_2**: at this pt think the question phrasing is not clear and does not match clarifications by questioner in comments as also reflected by responses & further questions from multiple commenters. the 1-3 criteria listed apparently dont completely capture what questioner is looking for. there is no ref to "impractical for small inputs" in the 1-3 item criteria but RB repeats it in comments. at this pt it might be better to start out from scratch with new carefully rephrased question also maybe after questioner reviews the apparently related links & figures out if they are sufficient or not.  

---

## 0 answers

