Software can be compatible for the two desktops depending on what libraries you have installed. I think GNOME uses GTK and KDE uses TCL. Some software is specific to it's desktop environment, but that's pretty much only the utilities for said environment.
They are not two different OSes (trying to answer by your definition) because they till run the same software for everything else, but may not be abe to run a couple of things. Is a windows XP system with the .NET framework installed a different OS than a windows XP system without?