In this paper we consider the problem of routing the lightpaths of a logical topology of a WDM network on an arbitrary physical topology, such that the logical topology remains connected even after the failure of a physical link. In a recent paper, Modiano et. al. introduced the notion of survivable routing and established a necessary and sufficient condition for the existence survivable routes of a logical topology in a physical topology. In this paper we show that problem of determining whether survivable routing is possible for a logical topology in a given physical topology is an NP-Complete problem. Moreover, we show that the problem remains NP-complete, even when the logical topology is restricted to be a ring with a specific ordering of the nodes.