Какие гипотезы TCS были доказаны для простых чисел и малых значений, но затем оказались ложными?

17

Существуют ли какие-либо предположения в теоретической информатике, которые включают некоторый параметр n и были доказаны для малых значений n AND для простых чисел, но позже оказались ложными?

В теории чисел такие проблемы существуют, например. как Аарон Мейеровиц указывает на один из коэффициентов циклотомических полиномов. Из TCS я знаю только такие примеры, как гипотеза уклончивости , которые все еще не решены .

domotorp
источник

Ответы:

3

Примечание. Это больше похоже на расширенный комментарий, чем на ответ.

Вот проблема комбинаторики, чей статус похож на аромат гипотезы уклончивости:

Фон . Латинский квадрат порядка - это матрица n × n, в которой каждый элемент из {1,. , , , n} встречается ровно один раз в каждой строке и столбце. Два латинских квадрата порядка n называются ортогональными, если вы получаете n 2 различных упорядоченных пары при их наложении. Говорят, что набор латинских квадратов взаимно ортогональн, если каждая пара из них ортогональна. Пусть N ( n ) обозначает максимальное количество взаимно ортогональных латинских квадратов порядка n .NN×NNN2N(N)N

N(N)N-1NNN(N)знак равноN-1N

Jagadish
источник
4
N(6)знак равно1N(N)2N>6N(10)<9
1
Спасибо, Джагадиш, проблема в том, что это предположения, которые можно утверждать только для простых (степенных) с. Я ищу что-то, что БЫЛО предположить, чтобы быть верным для всех чисел, но оказалось ложным.
Домоторп
@domotorp Да, мой ответ не дает точного ответа на вопрос. Мне любопытно узнать, есть ли такие примеры самому, так что +1 за ваш вопрос.
Джагадиш,
3

п-1пNNзнак равно32

Лев Рейзин
источник