Qual é o problema aberto mais antigo do TCS?

36

Esse problema é inspirado nessa pergunta do MO , que achei muito interessante.

Qual é o problema aberto mais antigo do TCS?

Claramente, esta pergunta precisa de alguns esclarecimentos.

Primeiro, o que é TCS? Eu acho que a existência de números ímpares perfeitos não é TCS. Eu diria que o décimo problema de Hilbert é o TCS. Penso que problemas como "Podemos construir X com uma régua e uma bússola" também são TCS, pois estão solicitando um algoritmo em um modelo restrito de computação. Pode não haver uma maneira rigorosa de definir o que é um problema do TCS, mas use seu julgamento. Talvez um teste seja "Se isso for resolvido, provavelmente apareceria no STOC / FOCS? O pesquisador que o resolveu provavelmente seria um cientista da computação teórico?"

Segundo, o que é "mais antigo"? Quero dizer mais antigo por data. A data prevista também deve ser verificável, mas não acho que isso deva ser muito difícil.

Terceiro, o que é um "problema em aberto"? Por "problema aberto", quero dizer um problema que foi considerado especificamente aberto em algum momento. Talvez tenha aparecido no final de um artigo na seção de problemas abertos, ou talvez haja evidências de que algumas pessoas tenham trabalhado e falhado, ou talvez existam provas incorretas na literatura, o que sugere que ele foi estudado. Um exemplo de algo que não se encaixa nesse critério: "Os gregos estudaram os objetos X e Y. Z é claramente um objeto intermediário, certamente eles se perguntaram se ele poderia ser construído". Se não houver literatura sobre Z nesse período, não haverá um problema em aberto nesse período.

Quarto, o que quero dizer com "problema"? Quero dizer uma pergunta específica "sim / não", e não algo como "Caracterizar todos os objetos X com a propriedade Y", porque essas perguntas geralmente não têm uma resposta satisfatória. Muitas vezes haverá discordância quanto à questão de ter sido resolvida. Não vamos entrar em tais questões aqui. Se não é uma pergunta de sim / não, mas é claro que é realmente aberto, tudo bem também. (Caso isso não esteja claro, por "problema" quero dizer um problema formalmente declarado. Por favor, não converta algumas lendas populares sobre jogos de azar no século 16 em uma pergunta sobre BPP e PSPACE.)

Por fim, como essa não é uma pergunta da lista grande, poste uma resposta somente se você achar que é mais antiga que as respostas já postadas (ou se você acha que as respostas postadas não satisfazem alguma outra condição - como não são TCS, ou eles não estão abertos). Esta não é uma coleção indiscriminada de velhos problemas abertos.

Robin Kothari
fonte
13
"Qual é a melhor maneira de cozinhar carne?" Sob um modelo de computação em fogueira, qual é o melhor algoritmo para preparar comida? - relevante há milhares de anos, ainda relevante agora! Além disso, há muita literatura sobre o problema! (Desculpe, eu não pude resistir ;-))
Daniel Apon
3
Existe um deus? Pode ser um problema do TCS se puder ser resolvido por computadores.
Sariel Har-Peled
9
@ Daniel, 'qual é a melhor maneira de cortar um bolo' é uma questão real da TCS !!!
Suresh Venkat
3
#offtopic: bom ver que supercooldave agora tem um nome :)
Suresh Venkat
5
Encontrei um livro intitulado "Uma história de algoritmos: do seixo ao microchip" ( amazon.com/dp/3540633693 ). Pode ser útil encontrar um histórico decente sobre algoritmos (novos e antigos).
MS Dousti 04/10/10

Respostas:

38

Qual é a complexidade computacional da multiplicação inteira? Indiscutivelmente, essa pergunta remonta pelo menos ao algoritmo de 'duplicação e mediação' para multiplicação de números inteiros descrito no Rhind Mathematics Papyrus, que foi escrito por volta de 1650 aC , mas afirma ser uma cópia de um documento significativamente mais antigo.

É certo que o papiro Rhind não considerou explicitamente a complexidade do seu algoritmo. Então, talvez uma resposta melhor seja: Qual é a complexidade de resolver sistemas de equações lineares? A pesquisa de algoritmos eficientes para resolver sistemas lineares remonta pelo menos ao comentário de Liu Hui, publicado em 263 dC , em Os nove capítulos da arte matemática . Especificamente, Liu Hui compara duas variantes do que agora é reconhecido como eliminação gaussiana e conta o número de operações aritméticas usadas por cada uma, com o objetivo explícito de encontrar o método mais eficiente.

Ambas as questões ainda são alvos de pesquisa ativa.

Jeffε
fonte
9
Ao contrário de Robin, não acho razoável insistir em que a questão tenha sido colocada em sua forma moderna. É como manter provas históricas nos padrões contemporâneos de rigor. Por esse padrão, a geometria axiomática começou com Klein, e Euclides era apenas um cara grego que balançava a mão.
Jeffε
6
"Pelos modernos padrões de rigor, Euclides era apenas um cara grego que acenava com as mãos": esse é o meu próximo .sig :)
Suresh Venkat
2
Eu acho que esses exemplos são bons. O que eu queria evitar era o que acontecia no excesso de matemática: havia uma discussão sobre se os gregos consideravam algum problema apenas porque haviam estudado algum problema relacionado. A outra coisa que quero evitar são questões filosóficas como "O universo é determinístico" sendo convertido no problema P versus BPP. Você forneceu um problema específico que foi considerado um problema computacional pelas pessoas que o colocaram, e isso é perfeitamente aceitável.
Robin Kothari
Esta questão foi parcialmente resolvida para multiplicação de números inteiros on-line. arxiv.org/abs/1101.0768
felix
23

A busca por um algoritmo eficiente para fatoração parece remontar a pelo menos Gauss. O artigo 329 das Disquitiones Arithmeticae de Gauss (1801) tinha a seguinte citação ( fonte ):

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length. ... Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.

Obviamente, é verdade que Gauss não definiu formalmente exatamente o que ele desejava do algoritmo de fatoração. Ele falou no mesmo artigo, porém, sobre o fato de que todos os algoritmos de teste de primalidade conhecidos na época eram muito "trabalhosos e prolixos".

arnab
fonte
2
Citação muito agradável. É ótimo como Gauss deixou claro que os atuais algoritmos de fatoração eram "trabalhosos e prolixos"!
Robin Kothari
10

O seguinte, citado de

  • Goldwasser, S. e Micali, S. 1982. Criptografia probabilística e como jogar pôquer mental, mantendo em segredo todas as informações parciais. Nos Anais do Décimo Quarto Simpósio Anual da ACM sobre Teoria da Computação (San Francisco, Califórnia, Estados Unidos, 05 a 07 de maio de 1982). STOC '82. ACM, Nova Iorque, NY, 365-377. DOI = http://doi.acm.org/10.1145/800070.802212

Refere-se a outro problema que remonta a Disquitiones Arithmeticae de Gauss (1801):

Se a fatoração de N não for conhecida e , onde(q(qN)=1denota o símbolo de Jacobi, então não há procedimento conhecido para decidir se q é um resíduo quadrático mod N. Este problema de decisão é bem conhecido por ser difícil na Teoria dos Números. É um dosquatroprincipaisproblemas algorítmicosdiscutidos por Gauss em seu "Disquisitiones Arithmeticae" (1801). Uma solução polinomial para isso implicaria uma solução polinomial para outros problemas em aberto na Teoria dos Números, como decidir se um N composto, cuja fatoração não é conhecida, é o produto de 2 ou 3 primos; veja os problemas abertos 9 e 15 emAdleman.(qN)

PS: Até agora, conhecemos dois dos quatro problemas algorítmicos :

  1. Factoring (como mencionado por arnab);
  2. Decidir a residência quadrática.

Quais são os dois problemas restantes descritos por Gauss?

MS Dousti
fonte
9

Na literatura de nosso país, há um ditado, que eu traduzo literalmente como "O enigma se torna fácil quando é resolvido". Embora não seja uma boa tradução, refere-se ao fato de que, quando você tiver a solução, poderá verificá-la facilmente; antes disso, o enigma parece muito difícil.

Isso se refere ao agora famoso problema "FP vs. FNP": Se FNP = FP, a verificação da resposta ao enigma é tão fácil quanto encontrá-lo. No entanto, se FNP ≠ FP, existem "enigmas" para os quais encontrar uma solução é muito mais difícil do que verificar a solução.

Acredito que esse problema seja o mais antigo problema aberto do TCS, mas sua formulação rigorosa remonta a apenas 30 anos atrás!

There seems to be a similar (yet somehow different!) proverb in the English language: "It's easy to be wise after the event" or "It's easy to be smart after the fact."

EDIT: "Podemos fatorar números no poli-tempo" é outro problema aberto do TCS, mas acho que é mais novo que o problema mencionado acima.

Aqui está duas listas de problemas abertos do TCS na Web:

Também temos essa lista aqui no CSTheory.

MS Dousti
fonte
1
Desde que eu estou restringindo-à formulações rigorosa dos problemas, eu acho que a questão de factoring e FP = FNP só pode ser formalizada uma vez que temos máquinas de Turing, e tempo polinomial, etc.
Robin Kothari
@Robin: Você não pode pedir velhos problemas formalizados do TCS, se não houvesse computadores na velhice! :)
MS Dousti
1
@Sadeq: Eu não me importo se a pergunta mais antiga for uma pergunta feita em 1922. Eu insisto em perguntas rigorosamente declaradas porque, caso contrário, as pessoas citarão textos de 4000 anos alegando que alguma frase sobre o universo era uma questão computacional disfarçado.
Robin Kothari
Em que ano esse problema foi formulado?
Dave Clarke
3
@Sadeq: Verdade, mas essa não é a questão P versus NP, a menos que alguém formalize o modelo, etc. Quero dizer que poderia igualmente representar alguma outra questão (digamos L contra NL, ou P / poli versus NP / poli, ou alguma pergunta em um campo diferente). Em segundo lugar, essa é uma crença comum, não algo considerado um problema em aberto. Não é algo que exija prova, em sua formulação original: é apenas uma observação sobre a vida.
Robin Kothari
3

Eu questiono sua teoria dos números excluídos, envolvendo questões sobre se alguns conjuntos teóricos dos números são finitos ou infinitos como parte do TCS e, definitivamente, argumentariam o contrário. os gregos questionaram se:

  • existem números perfeitos ímpares? [possivelmente considerado por euclides]

  • existe um número infinito de primos gêmeos?

TMxTMy que utiliza um grande limite superior na busca de um dos primos gêmeos encontrado após um par dos primos gêmeos antes. isso para?

então, sem dúvida, esses são dois problemas algorítmicos antigos e os gregos foram os pioneiros nos primeiros TCS, principalmente na forma de teoria dos números e os problemas da teoria dos números iniciais são apenas casos especiais de problema de parada de Turing e evidências circunstanciais precoces de sua dificuldade. e existe uma estreita relação entre perguntar sobre / encontrar / procurar provas e a teoria da indecidibilidade.

indiscutivelmente, uma nova pesquisa está mostrando que a conjectura de Collatz, antes considerada uma curiosidade da teoria dos números, tem vínculos profundos com a teoria da computabilidade e pode estar no limite entre problemas indecidíveis e decidíveis. também o exemplo que você cita do décimo problema de hilberts mostra um vínculo muito fundamental entre a teoria dos números e o TCS.

duas outras questões algorítmicas antigas:

  • o que é um algoritmo eficiente ou mais eficiente para calcular o maior divisor comum do MDC?

  • o que é um algoritmo eficiente ou mais eficiente para calcular números primos?

concordamos que a 2ª questão está intimamente relacionada ao fatoração, mas não é a mesma coisa, é claro. foi considerado pela peneira e euclides de eratóstenes. é claro que recentemente foi demonstrado que ele está em P pelo AKS, mas mesmo assim o algoritmo não se mostrou totalmente ideal.

existe uma pesquisa TCS muito moderna sobre o algoritmo euclides gcd (ou seja, século 20) que mostrou que os números de fibonacci fornecem o pior desempenho possível. [não tenho certeza quem primeiro mostrou isso]

até que o algoritmo de euclides seja comprovadamente ideal, a computação sem dúvida eficiente do gcd ainda está aberta.

vzn
fonte
7
Não concordo com a maior parte do que você diz (o fato de que você pode construir todos os tipos de máquinas de Turing que parem se existirem objetos conjecturados não torna esses problemas de existência questões de computabilidade). mas no final você tem um bom argumento: gerar deterministicamente um primo em alguma faixa é uma versão moderna e razoável da antiga missão de encontrar uma "fórmula para primos". Gostaria upvote se você escrever uma resposta focada ao longo destas linhas
Sasho Nikolov
1
Concordo com o comentário acima: a conjectura de Poincare também pode ser formulada como um problema de parada para as máquinas de Turing, mas nenhum progresso foi feito usando técnicas especificamente da comunidade de CS. O mesmo pode ser dito para esse número de problemas teóricos, computacionalmente relevantes que possam ser.
Cody
2

Não tenho certeza da gravidade dessa resposta, mas ...

Realmente depende de quão amplamente você está disposto a definir sua pergunta.

Certamente "alguém pode construir uma máquina inteligente?" é a mais antiga questão aberta no CS que iniciou a ciência da computação, mas provavelmente é antiga por um milênio ou dois do que o CS. Não? (É uma questão de teoria, pois pede uma resposta - não para a própria máquina ...)

Uma referência natural à busca de uma máquina inteligente seria o Golem ... http://en.wikipedia.org/wiki/Golem#History

Sariel Har-Peled
fonte
0

Posso responder à sua pergunta com 100% de certeza por um período de tempo. Se considerarmos o período desde o artigo seminal de Hartmanis e Stearns até qualquer ponto no futuro, o problema mais antigo no TCS que ainda está aberto é:

Qual é a sobrecarga mínima necessária para a simulação de TMs determinísticas?

T2(n)T(n)registroT(n)

registroT(n)

chazisop
fonte
1
registroT(n)
1
PNP
1
Isso poderia servir de esclarecimento, para benefício de quem não conhece esses documentos em detalhes: Que tipo de MT está sendo simulado? Que tipo de máquina está fazendo a simulação?
Funkstar
Não acredito que seja necessário um esclarecimento. O fato de o modelo usado no primeiro artigo ser o multitape TM é um fato bem conhecido, pois contém algumas das principais definições do TCS, além de ser explicitamente mencionado no título do artigo de Hennie e Stearns.
chazisop
1
Sua formulação da questão em aberto ainda é muito vaga, na minha opinião. Embora seja bem sabido na comunidade do ToC que Hartmanis, Hennie e Stearns trabalham com TMs multitape, isso simplesmente torna sua resposta inútil para os de muitos outros campos do TCS. Você deve considerar pelo menos adicionar o qualificador "multitape" à pergunta. (E mesmo assim, você tem o problema que Hartmanis e Stearns simulação usa uma TM 1-fita, enquanto Hennie e Stearns simulação usa um TM 2-fita.)
Funkstar