zschoche

Quick question: what are the NP-hard problems in the database area?

It would be great if someone could precisely define what is the goal we would like to optimize. In mathematical terms.

Nit: if number n is given in binary representation in the input, then an O(n)-algorithm runs in exponential time as n is an exponential function of log(n). Hence, log(n)^O(1)-time algorithms for the Fibonacci number are reasonable to exist, unless the decision version of the Fibonacci number is NP-hard.

Well, it always depends on what you lookup i.e. how much time one needs to compute entries of the given lookup table. If it takes O(2^n) time , then payback comes quickly, where n is the input size. It’s good advice to be very skeptical if one drops general statements like that. Look for algorithms with the best worst -case time complexity is a good start. It will always win. Theory works. Question is only of big the input has to be in order to see that. Here, the fun part starts I guess.

Okay let (P,k) be a parameterized problem which admits a fixed-parameter algorithm with respect to k. That means you have an algorithm which runs in f(k)n time, where n is the input size and f is a function only depending on k (for example (2^k)*n). Hence, if your real-world instances have always a small k then you can solve arbitrary large instances. Note that one problem can have a lot of different parameters and not all admitting such an algorithm (unless the world is very different than we believe). Now let (P’,h) be another parameterized problem and you have a polynomial time reduction from P’ to P. Then, this reduction gives you a fixed-parameter algorithm for P’ with respect to h if the value of k in the reductions depends only on h and nothing else.

if a problem is NP-hard does not mean that each instance is hard to solve. From my experience many instances appearing in practice are easy to solve even if there very large. The problem with these instances is that it takes to much space to write done the SAT-formual. So you do not even get to the point where you would run the solver. But a simple problem specific search tree algorithm has no problem with solving it. Bottom line, if you really need to solve a NP-hard problem then you might want to look for fixed-parameter tractable algorithms.

In most cases, lambdas are rvalues. That can have an impact on its scope and lifetime.