7
$\begingroup$

Before asking my questions, allow me to begin with a separate example to help clarify what I'm driving at. For terms that are not defined formally, please interpret them as you feel would be most appropriate, and I welcome any attempts to modify this question so as to make it more interesting and/or understandable.

Background Example: Suppose you have Cartesian coordinates for $n$ different points $p_1, \ldots, p_n$ in the plane, and you want to find a point $p$ that minimizes $\sum_{i}^{n}|p-p_i|.$ (In other words, you want to find the "geometric median" for these $n$ points.)

Finding such a $p$ is trivial for $n = 1$ and $n = 2$, and well-known for $n = 3.$

Note that even for $n = 4,$ finding a general approach that leads to an exact answer is tough. For larger values, say, $n = 10,$ we would (in most real life situations) estimate $p$ using a computer.

But here's a way to estimate $p$ using a physical model: take a piece of plexi-glass, draw a grid on it, drill tiny holes corresponding to the $n$ points, thread equally-weighted wires through each of the holes (tie, say, a $10g$ weight to the ends below the plexi-glass), and fuse the tops of all the wires together. Holding the plexi-glass level, a minimal energy argument suggests that the final resting point for this "fused top" will be (approximately, because we're talking about the real world here) at $p.$

Question 1: Is there some way to build a physical model where you start with a $9$x$9$ Sudoku grid and its clues (i.e. the numbers filled in at the start) and then separately have all the numbers yet to be placed, and by "doing something" (dropping balls, something with weighted-strings, I'm not sure -- hence the question) release the non-placed numbers so that they "quickly" fall into place (e.g. as a "minimal energy" or "path of least resistance" consequence)?

Remark: On the one hand, Sudoku is "discrete" in a way that the aforementioned background example is not, which suggests to me that it might be possible to create such a physical model. On the other hand, the $NP$-completeness of Sudoku has me nearly convinced that no such model could be built. However, I haven't the faintest idea as to how one proves the non-existence of this sort of physical model.

Question 2: What would the implications of the existence (or non-existence) of a physical model to "quickly" solve Sudoku be for the question of $P = NP$?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I am not sure this question is a good fit for MO. But, you might be interested in this paper by Scott Aaronson scottaaronson.com/papers/npcomplete.pdf $\endgroup$
    – user9072
    Commented Aug 14, 2012 at 20:02
  • 4
    $\begingroup$ Perhaps start with a 4x4 grid and see if there's a physical model that can solve that. It should be much simpler, since there are only 12 possible solutions up to permuting the entries. Non-existence in this case should be easier to do (maybe the models can't distinguish between two of the $4!*12$ solutions) and will imply the nonexistence of the larger solver, since you can embed the 4x4 grid into a 9x9 grid. $\endgroup$
    – Zack Wolske
    Commented Aug 14, 2012 at 21:36
  • 1
    $\begingroup$ If you mean by Sudoku being NP-complete a setting involving $n\times n$ Sudokus with $n$ tending to $\infty$, then that does not seem to have much relevance in the real life Sudoku where we only have $n=9$. $\endgroup$
    – timur
    Commented Aug 14, 2012 at 22:42
  • 8
    $\begingroup$ My brain is a physical system that can solve Sudokus. $\endgroup$
    – Steven Landsburg
    Commented Aug 15, 2012 at 5:35
  • 1
    $\begingroup$ Maybe such a computer should be called "analogue", to distinguish it from "digital". The classic example is sorting some (floating-point) numbers by size, by cutting rods (spaghetti?) to the various lengths, and standing all the rods on one end... $\endgroup$
    – paul garrett
    Commented Aug 15, 2012 at 16:49

2 Answers 2

Reset to default
3
$\begingroup$

I believe the so-called "adiabatic algorithm" fits your criteria, but perhaps not in the way you intend. In the adiabatic algorithm you encode the problem in a quantum Hamiltonian $H(s_1,s_2,\ldots,s_n)$ whose degrees of freedom are, say, Ising spins, in such a way that the ground state of $H$ is a simple product $|+\rangle|-\rangle...|+\rangle$, where the $\pm$ are bits encoding the solution. You bring the system to the ground state of $H$ by using a time-dependent Hamiltonian $H_t = (t/\tau) H + (1-t/\tau) H_0$, where $H_0$ is some simple Hamiltonian whose ground is well known is easily prepared at $t=0$. If $\tau$ is large enough, the final state at $t=\tau$ will be mostly in the ground state of $H$.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ I could use essentially the same argument for a normal computer: it is a physical system that can solve Sudoku (I have used a Sudoku solver in MATLAB, even). The "only" difficulty is in the logical interpretation of the system configuration. $\endgroup$
    – Steve Huntsman
    Commented Aug 14, 2012 at 23:48
  • 1
    $\begingroup$ What do you mean by "exactly the same argument?" The solution to a Sudoku puzzle is in no way the ground state of a normal computer. $\endgroup$
    – Yoav Kallus
    Commented Jun 21, 2013 at 14:40
0
$\begingroup$

Maybe this paper does what you are looking for ? Optimization hardness as transient chaos in an analog approach to constraint satisfaction M Ercsey-Ravasz, Z Toroczkai - Nature Physics, 2011 http://arxiv.org/pdf/1208.0526.pdf

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .