Hello. I think this is a current research area. I suggest you look in the IEEE literature, particularly the IEEE Signal Processing Magazine, which I think had a special issue a while ago on speech and music processing. In general, it would appear to be an extremely challenging signal processing problem. In specific cases, however, it might be easier. For instance if you have a polyphonic (multichannel) recording in which only certain audio signals are present on certain channels, then it might be a lot easier (like Karaoke).

Recently I was at a signal processing workshop and one of the topics, Blind source separation was discussed. I have attached the presentation for your reference. if you go through that you will find references to some algorithms/. I hope this helps.

As the previous answers mentioned, this is an active research topic and a challenging problem.  In general I think you need more than one microphone.  Related topics/algorithms that you can look for are the cocktail party problem, independent component analysis (ICA), and blind source separation.

The problem is that the frequency range of music and speech are overlapping. And if you want to separate one form the other you will affect the other signal of interest. Adaptive filtering is used for separating speech and background noise but in this case you have also a reference signal(microphone) that is a clean signal either the speech or the music. I would be also interested in a solution where you can separate it from a given signal without any reference signal.

This is a tough one. I'm thinking a least-mean-squares (LMS) algorithm, in an adaptive line enhancer configuration. So get a (good) vocalist to sing the voice part. Supply that as the "reference" signal. Then like 'magic', the LMS filter removes this signal from your song!