202503091503

Tags : Complexity Theory

PTAS

---

Definition

Polynomial Time Approximation Scheme is class of problems such that for any $ϵ$, there is a polynomial time algorithm that guarantees a $1+ϵ$ approximate solution.

Theorem

$\text{PTAS}\subseteq \text{APX}$ and the we have that $\text{PTAS}=\text{APX}$ iff $\text{P}=\text{NP}$

---

References

APX (Complexity Class) NP (Complexity Class) P (Complexity Class)