PhysX is used in several game engines, and it works perfectly fine regardless of video card brand.
People often confuse "GPU accelerated PhysX" with "PhysX". PhysX will work on the CPU, GPU accelerated PhysX requires an Nvidia card to use that feature.
In either case, you have to have the PhysX drivers installed. If you removed that game and reinstalled it, it would most likely install a version of the PhysX drivers, but going directly to Nvidia for the latest versions may be better.