Exact solutions to NP-hard problems

[cur...@uwpg02.uwinnipeg.ca]

Hello Net:

It is generally assumed that P<>NP;in other words, searching for efficient
algorithms solving NP-hard problems is assumed to be pretty much a waste
of time. Nevertheless, it must sometimes be desirable to solve NP-hard
problems exactly. For example, if you're were testing a heuristic algorithm
for Travelling Salesman it would be nice to have a selection of exactly
solved problems on hand for comparison purposes.

What has been done in this area? References would be appreciated, but
even better would be a nice pithy summary.

Thanks,

J. Currie
cur...@uwpg02.uwinnipeg.ca

[Greg Kuperberg]

In article <6SEP93....@uwpg02.uwinnipeg.ca> cur...@uwpg02.uwinnipeg.ca writes:
>It is generally assumed that P<>NP;in other words, searching for efficient
>algorithms solving NP-hard problems is assumed to be pretty much a waste
>of time.

It takes naivete to declare that a problem does not merit a clever
algorithm because it is computationally hard. In practice,
the computationally hard problems merit more attention, not less.

A typical situation with an NP-hard problem is that there is an
obvious algorithm that takes time, say, C^n for some C, and
then there is an algorithm that borrows from a standard bag of
tricks that runs in time sqrt(C)^n = sqrt(C^n) = a lot faster.
Sometimes factorial running time is reduced to exponential, which
is a real win.

For example, suppose you want to count the number of 3-colorings
of a planar graph, which is NP-hard and maybe harder. An
obvious algorithm is to find each 3-coloring with a depth-first tree
search. A much better idea is to divide and conquer: Try to
find a small vertex cut set that divides the graph into two roughly equal
pieces. Summing over colorings of the cut set, count colorings on each
half and multiply. You can, moreover, apply the algorithm recursively
to the pieces of the graph.

Another approach, called "dynamic programming", is to start with
a nucleus of one vertex of the graph, and maintain a list of the
number of colorings of the interior for each coloring of the periphery
as you add vertices to the nucleus.

Another example of a hard problem is the permanent of a matrix,
which is the determinant with all plus signs. The obvious algorithm
is to sum all n! terms. More cleverly, if the matrix is M_ij,
you can form the polynomial

P(x_1,...,x_n) = product of (M_i1 x_1 + M_i2 x_2 + ... + M_in x_n)

The polynomial P has a term whose coefficient is the permanent.
You can extract this coefficient by taking the alternating sum
of P(+-1,+-1,...,+-1), which takes O(n^2 2^n) operations.

[C. T. McMullen]

>It is generally assumed that P<>NP;in other words, searching for efficient
>algorithms solving NP-hard problems is assumed to be pretty much a waste
>of time.

In many practical applications one *needs* the solutions to NP-hard
problems. For example, checking for tautology is a basic operation
in logic synthesis; algorithms for doing this appear in
"Logic minimization algorithms for VLSI synthesis", Brayton et al,
Kluwer Academic Publishers, 1984.

Although these tautology algorithms are based on some simple-minded heuristics,
they yield exact solutions. The aim of the heuristics is to get the
procedures to execute in a reasonable amount of time on many
reasonable examples.