2
$\begingroup$

I'm a physicist who works on inverse problems; I'll explain what these are by means of an example. Consider an object whose refractive index is known; then, the problem of computing scattered electromagnetic fields (also called the forward problem) has a unique solution (whose complexity is essentially that of solving a system of linear equations). The inverse problem is one where one estimates the refractive index of an object given the measurements of the scattered electromagnetic fields.

The inverse problem is nonlinear, ill-posed, and ill-conditioned. Such a problem has no unique solution, and shows several local minima if attacked by local optimization techniques. Further more, if I am given a solution, I have no way of checking whether it is the best solution (say in a least squares sense) or not. How would I go about trying to find out, or even start to think, whether this problem is in NP?

I'd appreciate any pointers to appropriate resources if you think the question is too basic for this forum. Thanks!

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ NP only contains decision problems, that is, problems whose anwers are YES or NO. You would have to reformulate your question into such sdecision problem. $\endgroup$
    – Gamow
    Dec 9, 2015 at 18:37
  • 1
    $\begingroup$ You could add an extra parameter k and ask if there is an "estimation" with value k (or within a constant factor of k) then it becomes a decision problem. But I am not sure of how you formalize "estimation" and I am not sure how you would check the answer. Perhaps you just want to show such problems are NP-hard? (E.g. if you can solve them you can solve SAT) $\endgroup$
    – Ryan Williams
    Dec 9, 2015 at 19:35
  • $\begingroup$ Thanks @RyanWilliams . It should be possible to add an extra parameter, analogous to the radius of a norm ball in which the error (solution - estimate) should live. Having done so, checking the answer should also be straightforward. Now, if I want to show that such a problem is NP hard, how would I proceed? The coefficients in the above equations are not integers and are continuous valued. Thanks! $\endgroup$
    – xadu
    Dec 16, 2015 at 4:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.