Pseudo-polynomial time

Here's something I found when browsing a Wikipedia mirror:

http://www.reference.com/browse/wiki/Pseudo-polynomial_time

The best temperament finding algorithms may well be pseudo-polynomial. That would make them polynomial in, for instance, the number of equal temperaments you look at.

For us that's quite good enough. The number never gets very high and we're (well, I am , at least) more interested in the number of primes and generators than counting the bits used to represent the mappings.

Still, you may hear hardened number theorists tell you the problem is NP hard. In that case, don't panic! Simply stand your ground and no harm will come to you. It may be pseudo-polynomial after all.

Graham

--- In tuning-math@yahoogroups.com, Graham Breed <gbreed@...> wrote:
>
> Here's something I found when browsing a Wikipedia mirror:
>
> http://www.reference.com/browse/wiki/Pseudo-polynomial_time
>
> The best temperament finding algorithms may well be
> pseudo-polynomial. That would make them polynomial in, for
> instance, the number of equal temperaments you look at.
>
> For us that's quite good enough. The number never gets very
> high and we're (well, I am , at least) more interested in
> the number of primes and generators than counting the bits
> used to represent the mappings.
>
> Still, you may hear hardened number theorists tell you the
> problem is NP hard. In that case, don't panic! Simply
> stand your ground and no harm will come to you. It may be
> pseudo-polynomial after all.
>
>
> Graham

Is it NP-complete?

PGH

Paul G Hjelmstad wrote:

> Is it NP-complete?

According to Wikipedia, the knapsack problem is both NP-complete and has a pseudo-polynomial time solution. So it's possible. Specifically, this is the decision problem form.

The decision problem form of a temperament search would presumably be "is there a temperament with error less than such and such and complexity less than such and such?" As the knapsack problem seems to be the nearest famous problem to finding equal temperaments (both are linear Diophantine approximations) I'll guess they're both pseudo-polynomial. But then Wikipedia also says that some kinds of knapsack problem are polynomial so perhaps equal temperaments map to one of those (like perhaps finding TOP errors maps to the subset of linear programs that can be solved in polynomial time).

Finding higher rank temperaments is logically a problem of "simultaneous linear Diophantine approximations" (I think
Gene said this). But although it's easy to string the words together I haven't found anything about them. Maybe they're considered to be too difficult because the simpler case is already NP complete. But then for music theory purposes the numbers get big enough that you care about an efficient solution but not so big that it becomes impossible.

I'm open to the possibility that the formulation involving TOP-RMS errors and scalar complexity is an original approach to the general mathematical problem. If so, it looks interesting and mathematicians should be aware of the progress we're making. If not, I want to know what the standard theory says. Either way I need to find a tame number theorist to put it to.

It's also a lattice problem. Temperament classes are hypervolumes on the lattice. Good equal temperaments are short vectors -- and finding those is a problem of unknown complexity.

Graham