<p>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 <em>estimates</em> the refractive index of an object <em>given</em> the measurements of the scattered electromagnetic fields.</p>

<p>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?</p>

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

CC BY-SA 3.0
2015-12-09T18:37:00.620Z
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.
Gamow
CC BY-SA 3.0
2015-12-09T19:35:46.303Z
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)
Ryan Williams
CC BY-SA 3.0
2015-12-16T04:55:20.947Z
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!
xadu
<cc.complexity-theory><np><physics>
Are ill-posed inverse problems in NP?
xadu
# Are ill-posed inverse problems in NP?

(Asked by: username_0 on 2015-12-09)

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!

**Tags:** cc.complexity-theory, np, physics

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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)  
> **username_0**: 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!  

---

## 0 answers

