Mandelbrot set intersection decision problem

Is the intersection of the Mandelbrot set with a given region of the complex plane, say rectangular, non-empty? What is the computational complexity of this problem? How about instead of the Mandelbrot set exactly, we deal with the set of points which do not escape after, say, 1000 iterations?

Given the theorem that there are no isolated islands in the Mandelbrot set, it might be possible that this problem is solvable rapidly.