2
$\begingroup$

By "physical means", I mean, for example, using water pouring down tubes, or combining chemicals, etc. Basically, using some experiment in the physical world to perform some computation. I'll call this physical computation.

As the simplest example, if I want to add the numbers 3 and 5, I could just pour 3mL into a cup and 5mL into the same cup, and measure how many mL I end up with.

I know that physical computation will probably not be completely precise, but ignore that, and assume that all experiments and measurements are carried out at their theoretical perfect precision. Another way to think about it is that we have a perfect physics simulator that's efficient up to real time.

Let the class of problems that can be solved efficiently (in a polynomial number of steps) through physical computation be called Phys-P.

My question is: what is Phys-P's relation with P? Are there problems that physical compututation can solve faster than traditional computation? Does leveraging nature and physics give you an exponential speed-up? I'd like to think yes, but I can't think of a particular NP-hard problem that physical computation would solve efficiently. Maybe something like how the structure of a crystal that grows (given some initial conditions) will solve TSP, or something like that.

If possible, I'd like to keep BQP (e.g. quantum computation) out of the discussion, and focus on running physical/chemical experiments.

$\endgroup$
3
  • $\begingroup$ Note that $\mathsf{PP}$ is already the name of a complexity class. $\endgroup$
    – Nathaniel
    Jun 9, 2022 at 23:49
  • $\begingroup$ @Nathaniel good catch! Changed the suggested name to Phys-P $\endgroup$
    – chausies
    Jun 10, 2022 at 0:00
  • $\begingroup$ I think this is an interesting matter, but getting a meaningful definition of a class like Phys-P would be itself very hard. When does a physical processs solve some problem? What exactly is a single tep? $\endgroup$ Jun 10, 2022 at 8:03

2 Answers 2

3
$\begingroup$

It's not clear what "can be solved" actually means here. Let me explain with a real example.

It is known that NP-hard problems can be solved on an analog computer in polynomial time.

Suppose that you have a SAT problem in CNF with $m$ clauses and $n$ variables.

Define $c_{i,v}$ to equal $1$ if variable $v$ appears positively in clause $i$, $-1$ if variable $v$ appears negatively in clause $i$, and $0$ if it does not appear in clause $i$. So, for example, if this is clause $5$:

$$x_{3} \vee \bar{x}_{10} \vee x_{31}$$

Then $c_{5,3} = 1$, $c_{5,10} = -1$, $c_{5,31} = 1$, and for all other $j$, $c_{5,j} = 0$.

To find the solution to the SAT problem, we use spin variables $s_v$ where $s_v = -1$ if $x_v$ is false in a satisfying assignment, and $s_v = 1$ if $x_v$ is true in a satisfying assignment.

For each clause $j$ we define the function:

$$K_j(\vec{s}) = 2^{-k_j} \prod_{v} \left( 1 - s_v c_{j,v}\right)$$

where $k_j$ is the number of variables in clause $j$.

Notice that clause $j$ is satisfied exactly when $K_j(\vec{s}) = 0$. So this is a constrained optimisation problem, which has a standard solution by introducing Lagrange multiplier variables $a_j$. The Lagrangian is:

$$\mathcal{L}\left(\vec{a},\vec{s}\right) = \sum_{j} a_j K_j(\vec{s})^2$$

And a solution is any point where:

$$\nabla_{\vec{a},\vec{s}} \mathcal{L} = 0$$

The Lagrangian in this case is positive definite, so on an analog computer, you can solve this system using gradient descent. Make the variables $s_v$ and $a_j$ functions of time, and set up this system of differential equations:

$$\begin{eqnarray*}\frac{d s_v}{dt} & = & - \sum_{j} 2 a_j c_{j,v} \frac{K_j(\vec{s})^2}{1 - c_{j,v}s_{v}} \\ \frac{d a_j}{dt} & = & a_j K_j(\vec{s})\end{eqnarray*}$$

(Note that in the equations for $s_v$, you don't actually need circuitry to perform the division, since the divisor is a factor of $K_j$.)

This dynamical system, if implemented on an analog computer, will find the solution in polynomial time.

Oh, but there's a catch. There's always a catch. The formal solution for the Lagrange multiplier variables is

$$a_j(t) = a_j(0)\,e^{\int_{0}^{t} K_j\,dt'},$$

which is to say, the voltages become exponentially large over time if the problem is stiff.

So while SAT can indeed be solved in polynomial time on an analog computer, it's not clear that this computer is physically realisable in practice.

$\endgroup$
4
  • $\begingroup$ To be clear, the "analog computer" in this case would be a set of differential equations implemented by a physical circuit, yes? And in this example, the voltages become explosively large over time. But is it a proven fact that NP-hard problems can only be solved by analog computers if you allow for exponentially large usage of a physical resource (in this case, voltage)? Or is that just seemingly the case, and nothing's been proven one way or the other? $\endgroup$
    – chausies
    Jun 10, 2022 at 1:31
  • 1
    $\begingroup$ @chausies, no, nothing is proven. As far as we know, it is possible that P=NP, and then NP-complete problems can be solved without exponentially large amounts of any physical resource. It is widely believed that this is not the case, that P!=NP, but we have no proof of that... and so likewise we do not have any proof that an analog computer would require exponential amounts of some resource to solve a NP-complete problem. $\endgroup$
    – D.W.
    Jun 10, 2022 at 1:36
  • $\begingroup$ @D.W. is correct that nothing has been proven either way. My point is that what "efficient" means when you're talking about physical systems isn't always obvious. As another example, if you're talking about physical fluid in a physical pipe, there is a limit on how high the flow velocity can go. Most real fluids have a non-zero dynamic viscosity, so at some point you get turbulence. Even if you use a superfluid, at some later point you exceed its speed of sound, so you get shock phenomena. $\endgroup$
    – Pseudonym
    Jun 10, 2022 at 4:07
  • 1
    $\begingroup$ And to answer your question, "analog computer" means any physical system that models the differential equations, but yes, an electronic circuit is probably the easiest realisation. $\endgroup$
    – Pseudonym
    Jun 10, 2022 at 4:12
2
$\begingroup$

No one knows. The extended Church-Turing hypothesis is sometimes described as saying that the answer is Phys-P = BPP. This is a conjecture or hypothesis but it is not proven. The answer depends on the physics that underlies the universe. It is widely suspected (but not proven) that BPP = P. So, roughly speaking, the extended Church-Turing hypothesis amounts to saying that no physically realizable machine can give you more than a polynomial speedup.

We already know that the ECT is most likely not quite right, as we already believe that quantum physics is correct, not Newtonian physics. As a result, many expect that quantum computing is likely to disprove the ECT. But one can correct for this by conjecturing that Phys-P = BQP. As far as know, that conjecture could well be correct.

There are various exotic possibilities in which this hypothesis might be wrong. My favorite example is that, if time travel is possible, then we can compute anything in PSPACE in polynomial time. See Scott Aaronson's lecture notes or his earlier explanation. Alternatively, from a different perspective, if we live in a closed universe, then there is some constant upper bound on the maximum number of bits that can be stored in the universe ($10^{80}$ or something; the holographic bound), which implies that computation could be simulated by a finite-state machine -- not a very helpful point of view, and somewhat pedantic and nitpicky.

I suspect you might be interested in https://en.wikipedia.org/wiki/DNA_computing, even though it doesn't change the complexity class of what we can compute, and you might be interested in Scott Aaronson's comments on analog classical computers at https://scottaaronson.blog/?p=5517.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.