3

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 has an algorithm which runs in $O(39.51^n\cdot poly(n))$ time.

Community
  • 1
R B
  • 9,448
  • 5
  • 34
  • 74
  • 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 Jan 19 '14 at 19:18
  • 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 Jan 19 '14 at 20:31
  • @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 Jan 19 '14 at 20:52
  • @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 Jan 19 '14 at 21:33
  • @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 Jan 19 '14 at 21:40
  • @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. – R B Jan 19 '14 at 21:41
  • @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 Jan 19 '14 at 22:19
  • 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 Jan 19 '14 at 23:59
  • @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 ||^k$ steps seems like an unlikely candidate for even minor enhancements. – Yonatan N Jan 20 '14 at 04:02
  • @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 Jan 20 '14 at 06:43
  • @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 Jan 20 '14 at 06:46
  • 2
    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 problem which inspired in bioinformatic. As I know, best known exact algorithm for this is bigger than n!!. – Saeed Jan 20 '14 at 10:27
  • 1
    @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 Jan 20 '14 at 12:54
  • 1
    ok. re your last clarification think you are looking for something along lines of what RJLipton calls 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 – vzn Jan 20 '14 at 15:17
  • 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 Jan 20 '14 at 16:19

0 Answers0