Quais são as conjecturas do TCS que foram provadas para números primos e pequenos valores, mas depois se revelaram falsas?

Existem conjecturas na ciência da computação teórica que envolvam algum parâmetro n e foram provadas por pequenos valores de n E por números primos, mas depois se revelaram falsos?

Na teoria dos números, tais problemas existem, por exemplo. como Aaron Meyerowitz aponta aquele sobre os coeficientes dos polinômios ciclotômicos. No TCS, conheço apenas exemplos como a conjectura de evasão que ainda não foram resolvidos.

Nota: É mais um comentário estendido do que uma resposta.

Aqui está um problema da combinatória cujo status é semelhante ao da Evasiveness Conjecture:

Background . Um quadrado latino de ordem é um n × n matriz na qual cada elemento a partir de {1,. . . , n} ocorre exatamente uma vez em cada linha e coluna. Diz-se que dois quadrados latinos da ordem são ortogonais se você obtiver pares ordenados distintos quando os sobrepuser. Diz-se que um conjunto de quadrados latinos é mutuamente ortogonal se cada par deles for ortogonal. Seja o número máximo de quadrados latinos mutuamente ortogonais da ordem .$n$$n × n$$n$$n^2$$N(n)$$n$

Sabe-se que para todos os . Se é uma potência primária, sabemos que , mas para valores gerais de o status dos limites inferiores está aberto.$N(n)\leq n-1$$n$$n$$N(n)=n-1$$n$

Em uma resposta não muito parecida às do @ jagadish, depois de definidas, as matrizes de Costas foram rapidamente encontradas para números muito pequenos e posteriormente para os tamanhos , onde p é primo. No entanto, é aberto se eles existem para todos os n e computador pesquisas estão fazendo as pessoas acreditam que eles não existem para n = 32 .$p-1$$p$$n$$n=32$