Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Tag Info

### Theoretical explanations for practical success of SAT solvers?

I am assuming that you are referring to CDCL SAT solvers on benchmark data sets like those used in the SAT Competition. These programs are based on many heuristics and lots of optimization. There were ...
• 21.3k

### Theoretical explanations for practical success of SAT solvers?

I am typing this quite quickly due to severe time constraints (and didn't even get to responding earlier for the same reason), but I thought I would try to at least chip in with my two cents. I ...

### Theoretical explanations for practical success of SAT solvers?

Let me add my two cents of understanding to this, even though I've never actually worked in the area. You're asking one of two questions, "what are all the known approaches to proving theoretical ...

### Theoretical explanations for practical success of SAT solvers?

I'm not an expert in this area, but I think the random SAT / phase transition stuff is more or less completely unrelated to the industrial/practical applications stuff. E.g., the very good solvers ...
• 1,781

### Theoretical explanations for practical success of SAT solvers?

There is a paper "Relating Proof Complexity Measures and Practical Hardness of SAT" by Matti Järvisalo, Arie Matsliah, Jakob Nordström, and Stanislav Živný in CP '12 that attempts to link the hardness ...
• 4,501
Accepted

### Are there any heuristic-free NP complete problems?

See Josh Grochow's answer to Poly time superset of NP complete language with infinitely many strings excluded from it. According to that answer, under some natural cryptographic assumptions, for every ...
• 50.2k

### What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

An exponential upper bound has been given in Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber: A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings. Later the base of the ...
• 13.5k

### List of NP-hard problems, where there is active research in practical heuristics

MaxSAT - people actually care about this because SAT solvers are so well-developed that often the best route for your favorite NP optimization problem in practice is to reduce it to MaxSAT and then ...
Accepted

### Are there any heuristics that works solely on graphs?

There are known pre-processing methods that rely solely on the graph representation itself (and not on any kind of geometric embedding) to establish good heuristics for A*. Perhaps the most well-known ...

### Good algorithms to solve ATSP

You can also transform the ATSP to TSP; the process requires doubling number of nodes (adding dummy cities). http://www.sciencedirect.com/science/article/pii/0167637783900482 http://www.sciencedirect....

### Finding smallest context free grammar that generates a set of sets

Define a language $L$ to be nicely-ordered if $L \subseteq a^*b^*c^*d^*\cdots$, i.e., in every word of $L$, the letters appear solely in lexicographic order. Conjecture: the optimum is always ...
• 10.3k
Accepted

### Understanding performance of QFBV SMT solvers

The short answer is no, we don't understand it. The long answer is yes, we have some bounds, but those bounds aren't very helpful. It's quite clear that the worst-case running time is exponential. ...
• 10.3k

### Heuristic with worst-case exponential complexity

While there are many heuristics (arguably all of them) that take exponential time in the worst-case, what usually makes them attractive (and marketable) is that they "appear" to perform much better in ...
• 31.7k
Accepted

### TSP heuristics for limited distance information

There is no algorithm that runs in time $o(n^2)$ on an $n$-point metric space and returns a tour with weight within a constant factor of the minimum weight: see the argument in Section 9 of this paper ...

### Is this NP-Hard or does a known optimal polynomial time solution exist?

This problem is known as Weighted Set Packing and it is NP-complete. In order to see this, assign each customer a set with weight which equals the sum of the item values he asks for. The best known ...
• 9,358

### Heuristics for graph bisection

Besides basic Kerninghan-Lin algorithm (complexity $O(n^2 log(n))$), there's also Fiduccia-Mattheyses (1982) heuristic, which is a variant of Kerninghan-Lin with linear complexity $O(E)$, where $E$ is ...
• 121

### Theoretical study of coordinate descent methods

Note that in optimization, "convergence rate" usually means asymptotic behavior. That is, the rate only applies to the neighborhood of optimal solutions. In that sense, Luo & Tseng did prove ...
Accepted

### Pathfinding search over a space with known changing costs

In general, finding least-cost paths with arbitrary time-dependent edge costs is NP-hard, assuming that either (a) waiting at nodes is forbidden and your costs are not FIFO-preserving (e.g., see here ...
Accepted

### Packing $n$ objects into $m$ bins whose size is variable

One simple "bad" input that needs to be considered for worst-case analysis of this problem is as follows. Let $c=(\sqrt{17}-1)/2 \approx 1.56$. There are three objects of size $c$, $1$, and $1$. ...
• 18.7k

### Practical/heuristic algorithm for multi set-cover

You'd have to tweak the limits (in particular max_level may be too low), but for at least some "real" problems this is within the bounds of Knuth's algorithm M. ...
• 1,235
1 vote
Accepted

### Is it possible to prove that a general purpose integer factorization algorithm must contain a loop?

It depends on the precise model of computation you work within. However, this doesn't seem to be a useful direction for proving lower bounds on the time to factor. Uniform algorithms Let's look at ...
• 10.3k
1 vote

### List of NP-hard problems, where there is active research in practical heuristics

Operations research have a plenty of combinatorial optimization problems where the development of heuristics for minimization (or maximization) of resulting costs are an very active area. For example,...
1 vote

### Theoretical explanations for practical success of SAT solvers?

Since the original question title asks for theoretical explanations, let me point to a paper that might provide a kind of non-standard theoretical explanation. The main result of the paper is that one ...
• 10.7k
1 vote

### Finding smallest context free grammar that generates a set of sets

Because the order of your symbols does not matter, you can always move the nonterminals to the very right of the productions. If there is no more than one in any rule, the resulting grammar is regular....
1 vote

• 121
1 vote

### Literature for Generalized Load Balancing

Appreciable literature is available in this standard book on Approximation Algo by Vazirani http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf Refer to chapter 10 for details.
• 161
1 vote

### A search problem and no algorithm for it

As observed in Aaron Roth's answer, what you're describing does indeed appear to be PLS. In such cases, there are many, many alternative approaches under the heading of `metaheuristics'. A great ...

Only top scored, non community-wiki answers of a minimum length are eligible