Your second case there is still relatively easy to test! Consider the problem of intersecting two arbitrary 3D surfaces to get a curve. There are an infinite

Your second case there is still relatively easy to test! Consider the problem of intersecting two arbitrary 3D surfaces to get a curve. There are an infinite number of possible inputs. Except for rare simple cases, for each pair of inputs there are an infinite number of valid approximate solution curves AND an infinite number of ways to express each of those curves. Also, you want solutions which are well-behaved -- no kinks, no singularities, etc -- and as simple as reasonably possible (but no simpler). And even that's still better than something like MP3 encoding or digital musical instrument UI testing, where the quality of the result is arguably subjective...