Solving NP-complete Problems
At present, all known algorithms for NP-complete problems require time that is superpolynomial in the input size, and it is unknown whether there are any faster algorithms.
The following techniques can be applied to solve computational problems in general, and they often give rise to substantially faster algorithms:
- Approximation: Instead of searching for an optimal solution, search for an "almost" optimal one.
- Randomization: Use randomness to get a faster average running time, and allow the algorithm to fail with some small probability. Note: The Monte Carlo method is not an example of an efficient algorithm, although evolutionary approaches like Genetic algorithms may be.
- Restriction: By restricting the structure of the input (e.g., to planar graphs), faster algorithms are usually possible.
- Parameterization: Often there are fast algorithms if certain parameters of the input are fixed.
- Heuristic: An algorithm that works "reasonably well" in many cases, but for which there is no proof that it is both always fast and always produces a good result. Metaheuristic approaches are often used.
One example of a heuristic algorithm is a suboptimal greedy coloring algorithm used for graph coloring during the register allocation phase of some compilers, a technique called graph-coloring global register allocation. Each vertex is a variable, edges are drawn between variables which are being used at the same time, and colors indicate the register assigned to each variable. Because most RISC machines have a fairly large number of general-purpose registers, even a heuristic approach is effective for this application.
Read more about this topic: NP-complete
Famous quotes containing the words solving and/or problems:
“Science is a dynamic undertaking directed to lowering the degree of the empiricism involved in solving problems; or, if you prefer, science is a process of fabricating a web of interconnected concepts and conceptual schemes arising from experiments and observations and fruitful of further experiments and observations.”
—James Conant (1893–1978)
“If when a businessman speaks of minority employment, or air pollution, or poverty, he speaks in the language of a certified public accountant analyzing a corporate balance sheet, who is to know that he understands the human problems behind the statistical ones? If the businessman would stop talking like a computer printout or a page from the corporate annual report, other people would stop thinking he had a cash register for a heart. It is as simple as that—but that isn’t simple.”
—Louis B. Lundborg (1906–1981)