Miklós Ajtai (Budapeste, 2 de julho de 1946) é um cientista da computação húngaro.
Trabalha no IBM Almaden Research Center, Estados Unidos.
Em 2003 recebeu o Prêmio Knuth, por seus diversos trabalhos em ciência da computação, incluindo um algoritmo clássico de classificação de rede (desenvolvido juntamente com János Komlós e Endre Szemerédi), ínfimo exponencial, implicações tempo-espaço superlineares para ramificação de programas, o outros resultados.
Vida Ajtai graduou-se em 1976 na Academia de Ciências da Hungria,Magyar Tudományos Akadémia, Almanach, 1986, Budapest. da qual é desde 1995 um membro externo.
Resultados selecionados Um dos resultados de Ajtai estabelece que o comprimento das provas em lógica proposicional do princípio da casa dos pombos para n itens cresce mais rápido que qualquer polinômio em n. Também provou a afirmação que "quaisquer duas estruturas de interpretação contáveis que são equivalentes de segunda ordem são também isomórficas" é consistente com e independente dos axiomas de Zermelo-Fraenkel. Ajtai e Endre Szemerédi provaram o teorema dos vértices (corners theorem), um passo fundamental para generalizações dimensionais superiores do teorema de Szemerédi. Juntamente com János Komlós e Endre Szemerédi provou o limite superior ct2/log t do número de Ramsey R(3,t). O correspondente limite inferior foi provado por Jeong Han Kim somente em 1995, o que lhe valeu um Prêmio Fulkerson. Com Václav Chvátal, M. M. Newborn e Endre Szemerédi, Ajtai provou que um grafo planar com n vértices e m arestas, sendo , tem no mínimo crossings.
Publicações selecionadas . .
Ligações externas
Categoria:Prêmio Knuth Categoria:Membros da Academia de Ciências da Hungria Categoria:Teóricos da informação Categoria:Matemáticos da Hungria Categoria:Cientistas da computação da Hungria Categoria:Cientistas da computação dos Estados Unidos Categoria:IBM Categoria:Membros da Academia Nacional de Ciências dos Estados Unidos