Interestingly, dependency resolution is not the only NP hard problem uv tries to solve. During development, it also became clear that we needed some way to simplify PEP 508 marker expressions and ask questions like, “are these marker expressions disjoint?”

See: https://github.com/astral-sh/uv/blob/72bd12716225ae48d1e46ec6254d7daf134bdc94/crates/pep508-rs/src/marker/algebra.rs