Inapproximable

Inapproximable refers to a concept in mathematics and computer science that pertains to problems or functions that cannot be approximated to within a certain degree of accuracy by any algorithm or computational process. This notion is closely related to the concept of computational complexity and the theory of approximation algorithms.

In the context of optimization problems, an inapproximable problem is one for which no polynomial-time algorithm can find a solution that is within a certain factor of the optimal solution. For example, the Traveling Salesman Problem (TSP) is known to be inapproximable within a factor of 1.5 unless P=NP, meaning that no efficient algorithm can guarantee a solution that is within 50% of the optimal tour length.

In computational complexity theory, a problem is considered inapproximable if there exists a constant ε > 0 such that no polynomial-time algorithm can approximate the solution to within a factor of 1+ε of the optimal solution, unless P=NP. This is often referred to as an APX-hard problem, where APX stands for Approximation Polynomial-time.

Inapproximability results are typically proven using reductions from known hard problems. For instance, the result that TSP cannot be approximated within a factor of 1.5 can be shown by reducing the problem of finding a Hamiltonian cycle in a graph to TSP.

The study of inapproximability is important in computer science as it helps in understanding the limits of what can be efficiently computed. It also guides the design of approximation algorithms and provides insights into the inherent difficulty of certain problems.