Classical General Relativity (GR) together with conventional equations of state suggest that in complete gravitational collapse a singular state of matter with infinite density could be reached finally, to what is popularly called a "black hole." In addition to its interior singularities, in which space and time itself are crushed out of existence, the main characteristic feature of a black hole is its apparent horizon, the surface of finite area at which outwardly directed light rays are first trapped. The loss of information to the outside world this implies gives rise to additional difficulties with well-established principles of quantum mechanics and statistical physics. He will overview the historical and most recent approaches to these problems, as well as the status of the gravitational vacuum condensate star proposal made in 2001, and the implications the resolution of these issues will have for fundamental physics. The prospect of testing these ideas with astronomical observations in the next few years of Sag A*, the 4 million solar mass "black hole" in the center of our Milky Way galaxy and other "black hole" candidates will also be discussed.