On Jul 1, 2020, at 12:21 PM, Veit Elser <ve10@cornell.edu> wrote:
On Jun 30, 2020, at 11:06 PM, Cris Moore via math-fun <math-fun@mailman.xmission.com> wrote:
That is, if one choice would lead to more than one solution, or none at all, I reasoned that it would lead to none at all — and I took the other choice. The same thing comes up in Sudoku and its variants.
I’m not sure I follow. Perhaps you are using symmetry? For example, there are some (>1) symmetry-related choices and one other choice (not related by symmetry to the others). The promise of uniqueness then compels you to choose the odd-man-out.
Right. In Alcazar, for instance, you have to draw a Hamiltonian path through a chamber with obstacles, and there are often subchambers with multiple entrances and exits. If some entrance-exit pair would allow you to draw this path in two different ways, that must not be the right way to go.
There is a class of optimization problems where one knows in advance that the optimum is exceptionally good, either by human design (crypt problems) or natural design/evolution (proteins). Usually such problems have unique solutions (up to symmetry). For such problems I would think that optimization algorithms that do not take advantage of this information are suboptimal to ones that do.
Yes. As another example, the best known algorithm for SAT with unique solutions is faster than the best known for SAT in general (both exponential but the former has a smaller exponent). - Cris
-Veit
Cris Moore moore@santafe.edu The real danger is that such machines, though helpless by themselves, may be used by a block of human beings to increase their control over the rest of the race or that political leaders may attempt to control their populations through political techniques as narrow and indifferent to human possibility as if they had, in fact, been conceived mechanically. — Norbert Wiener