[obm-l] Numeros primos - solução
Três cientistas da computação chocaram a comunidade de matemáticos ao encontrar a solução para um problema que dura séculos: como dizer se um número é primo. Aprova é impressionante em sua simplicidade, e fez os matemáticos se perguntarem o que mais eles podem ter deixado passar.Os números primos, que são divisíveis apenas por si mesmos e 1, são blocos de construção fundamentais da matemática e fascinam estudiosos desde os temposantigos. Em 240 a.C., o matemático grego Eratóstenes apresentou a primeira forma à prova de falhas para saber se um número era primo. Mas o tempo que o método exige cresce exponencialmente com o tamanho do número, de forma que para números muito longos é necessário mais tempo que a idade do Universo parasolucionar o problema. Desde então os matemáticos têm tentado encontrar um algoritmo de tempo polinomial, capaz de fornecer uma resposta em uma quantidadede tempo razoável.A busca se intensificou ao longo das últimas poucas décadas, desde que os números primos se tornaram vitais para a criptografia. O sistema de encriptação usado para proteger transações pela Internet conta com o fato de serextremamente difícil descobrir os fatores de grandes números primos. Os algoritmos usados atualmente para ajudar a encontrar estes fatores são rápidos, mas eles apenas fornecem a probabilidade de um número ser primo ou não.Apesar da probabilidade ser muito alta, estes algoritmos não representam uma prova. Agora Manindra Agrawal e seus alunos ainda não formados, Neeraj Kayal e Nitin Saxtena, foram bem-sucedidos onde as melhores mentes da matemáticafracassaram.O trio, do Departamento de Ciência da Computação e Engenharia do Instituto Indiano de Tecnologia em Kanpur, desenvolveram um algoritmo que dá uma resposta definitiva para o problema em tempo razoável.O sucesso deles está na nova abordagem que adotaram para o problema. Em vez de fazer a grande pergunta, "este é um número primo?", eles geraram uma sériede perguntas menores ou "igualdades" do número que está sendo testado. "Se as igualdades se sustentarem, o número é primo, se alguma delas não sesustentar, então o número não é primo", explica Agrawal.Até o momento milhares de matemáticos verificaram as provas postadas atualmente no site do instituto na Internet. "Todos os que me mandaram e-mails apreciaramo algoritmo e disseram que ele está correto", diz Agrawal para a New Scientist.Especialistas suspeitavam que um algoritmo de tempo polinomial fosse possível. Mas não previam a simplicidade da solução em 13 linhas que Agrawal e seus colegas apresentaram. "É uma bela solução e estou muito feliz por eles, mas estou um pouco embaraçado por não ter visto isto eu mesmo", diz o especialista em números primos Carl Pomerance, dos Laboratórios Bell da Lucent, em NovaJersey. "A solução deles é simples. Isto não quer dizer que seja trivial; o que eles fizeram foi muito inteligente", acrescenta.O avanço teórico é significativo por si só, mas Ian Stewart da Universidade de Warwick disse que o método também deverá ajudar os matemáticos a solucionarem outros problemas, nos quais chegaram a um beco sem saída usando outras técnicas.A segurança na Internet ainda não está sob ameaça. "A solução provavelmente terá um impacto muito pequeno, pois ela não oferece nenhuma vantagem real sobreos algoritmos probabilísticos já usados no setor", afirma Ben Hadley da nCipher, uma empresa de segurança por criptografia baseada em Cambridge. Mas Pomerance acredita que a existência da prova deixará os criptologistas preocupados. "Se há um teste simples para saber se um número é primo, também pode haver uma forma simples de determinar os fatores primos que stamosatualmente investigando", disse ele.Esta é a verdadeira importância do trabalho do trio. O fato de estudantes não formados, trabalhando em seu projeto de fim de ano, poderem solucionar um enigma tão antigo levanta a possibilidade de que outras soluções simples para grandes problemas matemáticos podem ter sido ignoradas. "É um lembrete de como podemos ignorar as coisas simples", disse Pomerance.Tradução: George El Khouri Andolfato15/08/2002 - 15h53http://www.uol.com.br/inovacao/ultimas/ult762u636.shl
Re: [obm-l] (sem assunto)
3) n = 4k A partir daqui, = significa congruo modulo 10 1^n = 1 (mod 10) 2^n = 16 ^k = 6^k = 6 3^n = 81^k = 1^k = 1 4^n = 254^k = 6^k = 6 5^n = 5 6^n = 6 7^n = 2401^k = 1 8^n = 4096^k = 6^k = 6 9^n = 81^(2k) = 1^(2k) = 1 A soma eh congrua a 1+6+1+6+5+6+1+6+1 = 33 que eh congruo a 3. Resposta: 3 Bruno F. C. Leite wrote: At 23:02 24/08/02 -0400, you wrote: Olá rapaziada...vai ai um..se alguem puder ajudar. 1)Prove que existem infinitos primos p tais que sejam congruos a 3 modulo 4. Acho que já madei uma solução deste problema para a lista, dê uma olhada nos arquivos! 2)Qual o resto da divisão euclidiana de s=1^5+2^5+3^5+...+99^5+100^5 por 4?? Justifique. Observe que você pode ignorar os números pares da soma: todos eles (2^5, 4^5, etc) são multiplos de 4. Para os impares, observe que (4k+1)^5+(4k+3)^5 é sempre multiplo de 4... Bruno Leite http://www.ime.usp.br/~brleite 3)Se n é um multiplo de 4, qual o resto da divisão de 1^n+2^n++8^n+9^n por 10? Valeu = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] ajuda !!
olá! ei, como faço pra estimar a qnt. de dígitos de ^ ? (e pq q eh menor q 4* ?) -- bem, realmente eh facil ver q ^ tem menos q 4* +1 digitos, pois 10^4 , mas ainda fica uma aproximação ruim (apesar de q com essa estimativa dê pra fzer o problema), dai tentei fzer 10^4/2 = ^10^4*/2^, daí usando log2=0,301 (acho q eh isso) pode-se ter uma aproximação melhor eu acho, mas como melhorar mais um pouco esta aproximação? e como saber se a aproximação q temos eh suficiente pra resolver a questão?? aproveitando a deixa, como provo q se x1=x2=...=xn e y1=y2=...=yn , e zi uma permutação de yi (i=1,...,n), então sum(xiyi)=sum(xizi) (i=1,...,n) ??? thanks! fê! _ Converse com seus amigos online, faça o download grátis do MSN Messenger: http://messenger.msn.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Duas questões do IME.
2) Se sao n clubes nao fluminenses, o total de pontos eh 8+kn. Mas isso eh igual ao total de jogos, Cn+2,2 = (n+2)(n+1)/2. Igualando, k = (n+3)/2 - 7/n. 2k eh inteiro. 2k= n+3 - 14/n. Entao n so pode ser 1 ou 2 ou 7 ou 14. n=1 e n=2 sao absurdos pois k seria negativo. Logo, n=7 ou n=14. Bem, agora vou propor outro problema. Esta soluao estah correta ou nao? [EMAIL PROTECTED] wrote: Ol pessoal da lista,gostaria de uma ajuda nessas duas questes do IME. 1) 12 cavaleiros esto sentados em torno de uma mesa redonda .Cada um dos doze cavaleiros considera seus dois vizinhos como rivais.Deseja-se formar um grupo de 5 cavaleiros para libertar uma princesa.Nesse grupo no poder haver cavaleiros rivais .Determine de quantas maneiras possvel escolher esse grupo. 2) Dois clubes do Rio de Janeiro participaram de um campeonato nacional de futebol de salo onde cada vitria valia 1 ponto,cada empate meio ponto e cada derrota zero ponto.Sabendo que cada participante enfrentou todos os outros apenas uma vez,que os clubes do Rio de Janeiro totalizaram,em conjunto, 8 pontos e que cada um dos outros clubes alcanou a mesma quantidade k de pontos, determine a quantidade de clubes que participou do torneio. Um abrao, Bruno Moss.
[obm-l] Grau 5
Como pode ser tão simples encontrar soluções para as equações de grau 3 e 4 e ser impossível encontrar solução para Grau 5 ?? Mathematicus nascitur, non fit Matemáticos não são feitos, eles nascem --- Gabriel Haeser www.gabas.cjb.net -- Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Relativamente Primos???
Nunca tinha ouvido falar, mas em todo caso peço ajuda. 1) Provar que 4k+3 e 5k+4 são relativamente primos, para todo inteiro k. Isto se torna bem simples se vc usar o fato abaixo. Vou esccrever mdc(a,b) simplesmente como (a,b). --Se a, b e c são inteiros (a,b)=(a,b+ac). logo esccrveemos (4k+3,5k+4)=(4k+3,5k+4-4k-3)=(4k+3,k+1)=(4k+3-3k-3,k+1)=(k,k+1)=(k,1)=1. []'s. Marcelo _ Send and receive Hotmail on your mobile device: http://mobile.msn.com = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Política NAO é assunto da lista. - SPAM - não vote nesse SPAMEIRO
Se me permitem dizer, este foi um dos piores off-topic que a lista ja teve.Utilizar a lista para divulgacao politica e incorreto, afinal, aqui e o unico lugar onde nos vemos livres de toda lavagem cerebral que os politicos fazem por meio da televisao e do radio. Peço apenas um pouco de respeito, so isso, respeito com os colegas da lista e um pouco de conveniencia. O objetivo da lista e bem claro-estamos aqui para discutir problemas de matematica! Agora e triste abrir uma mensagem e descobrir que o unico lugar a salvo de todas as corrupcoes foi violado bruscamente por uma mensagem desse tipo. Espero que as pessoas respeitem mais a nossa lista, caso contrario, daqui ha pouco, ela sera ate mesmo veiculo de vendas... abraços Marcelo From: Eduardo Azevedo [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] Política NAO é assunto da lista. - SPAM - não vote nesse SPAMEIRO Date: Sun, 25 Aug 2002 02:32:53 -0300 Se não tem vergonha devia ter. Uma mula como você pode achar que política e matemática são a mesma coisa, mas não são. O Manoel pode trabalhar muito no interior do Estado(nem sei qual), mas pra minha vida ele só trouxe SPAM. Esse é um candidato em quem eu não voto, e se vir alguém votando, logo falo pra não votar. OBS: Ser ousado é outra coisa. Você é só sem vergonha mesmo. [EMAIL PROTECTED] = SPAM SPAMMER = mail bomb Original Message - From: ReNNeR To: [OBM] Sent: Sunday, August 25, 2002 12:59 AM Subject: [obm-l] Política também é assunto da lista. Meus amigos da lista, Acreditando que a matemática, assim como diversas outras áreas do conhecimento, é diretamente relacionada à estrutura pública que o pais possui, seja nos cargos executivos, legislativos ou judiciários, indico o nome do Manoel Veras como deputado estadual. Conheço o seu trabalho e a sua vontade para melhorar a vida das pessoas, principalmente no interior do Estado que ainda sofre diversos problemas sociais e enfrenta uma eduação de qualidade não muito boa. Apesar de esse não ser o dever direto de um Deputado, o Manoel sempre se preocupou e procurou soluções para esses tipos de problemas. Não tenho vergonha de ser ousado e pedir, além do seu voto, o seu apoio a essa candidatura, pois se trata de um Deputado que faz por merecer! Obrigado e não esqueça: Manoel Veras - 45145 _ Chat with friends online, try MSN Messenger: http://messenger.msn.com = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
RES: [obm-l] ajuda !!
Fernanda, Para sabermos a quantidade de dígitos de um número N (N inteiro maior que ou igual a 1) e não múltiplo de 10, basta pegarmos a parte inteira do logarítmo na base 10 de N e adicionarmos 1. Se N é múltiplo de 10, o número de dígitos é o próprio valor do logarítmo. Seja N = ^ e n o número de dígitos de N. Antes de calcularmos, é interessante perceber que n está entre 3* + 1 e 4* + 1, pois 10^3 10^4. logN = *log() logN = 16210,70787939468 Portanto n = 16210 + 1 = 16211 dígitos. Veja que 1 n 1. Obs: 1) Se esta for uma questão de prova/concurso/olimpíada, onde não é permitido o uso de calculadoras, deveremos proceder da seguinte forma: logN = *log(4*11*101) logN = *(log4 + log11 + log101) logN = *(2*log2 + log11 + log101) Neste caso, deveriam ser dados os valores de log2, log11 e log101 (pois são números primos) com casas decimais suficientes para levar em consideração a grandeza de . 2) Você fala em estimativa ou aproximação de n. Por que aproximar ou estimar, se podemos calcular exatamente? Edilon Ribeiro. -Mensagem original- De: Fernanda Medeiros [mailto:[EMAIL PROTECTED]] Enviada: dom 25/8/2002 10:21 Para: [EMAIL PROTECTED] Cc: Assunto: [obm-l] ajuda !! olá! ei, como faço pra estimar a qnt. de dígitos de ^ ? (e pq q eh menor q 4* ?) -- bem, realmente eh facil ver q ^ tem menos q 4* +1 digitos, pois 10^4 , mas ainda fica uma aproximação ruim (apesar de q com essa estimativa dê pra fzer o problema), dai tentei fzer 10^4/2 = ^10^4*/2^, daí usando log2=0,301 (acho q eh isso) pode-se ter uma aproximação melhor eu acho, mas como melhorar mais um pouco esta aproximação? e como saber se a aproximação q temos eh suficiente pra resolver a questão?? aproveitando a deixa, como provo q se x1=x2=...=xn e y1=y2=...=yn , e zi uma permutação de yi (i=1,...,n), então sum(xiyi)=sum(xizi) (i=1,...,n) ??? thanks! fê! _ Converse com seus amigos online, faça o download grátis do MSN Messenger: http://messenger.msn.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] = winmail.dat Description: application/ms-tnef
[obm-l] função
Oi pessoal; Será que alguem poderia me ajudar com os seguintes problemas : 1) Seja f:R-R uma função não identicamente nula, tal que f(1)=0 e 2f(x)f(y)=[f(x+y)+f(x-y)] ; para x e y pertencentes a R. a) quais os valores de f(0); f(2); f(3) b) mostre que f(x+4)=f(x) ; para qualquer x E R. 2) Seja f:R-R uma função tal que f(x)=x^2-3x+4. Quantas soluções reais tem a equação f(f(f...f(x)...))=2, onde f é aplicada 2002 vezes ? Obrigado ... Carlos. __ AcessoBOL, só R$ 9,90! O menor preço do mercado! Assine já! http://www.bol.com.br/acessobol = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] ajuda !!
At 13:21 25/08/02 +, you wrote: olá! ei, como faço pra estimar a qnt. de dígitos de ^ ? (e pq q eh menor q 4* ?) -- bem, realmente eh facil ver q ^ tem menos q 4* +1 digitos, pois 10^4 , mas ainda fica uma aproximação ruim (apesar de q com essa estimativa dê pra fzer o problema), dai tentei fzer 10^4/2 = ^10^4*/2^, daí usando log2=0,301 (acho q eh isso) pode-se ter uma aproximação melhor eu acho, mas como melhorar mais um pouco esta aproximação? e como saber se a aproximação q temos eh suficiente pra resolver a questão?? aproveitando a deixa, como provo q se x1=x2=...=xn e y1=y2=...=yn , e zi uma permutação de yi (i=1,...,n), então sum(xiyi)=sum(xizi) (i=1,...,n) ??? Oi, Esssa é a desigualdade do rearranjo. Tem numa eureka, eu acho que 5 ou 6. (veja o artigo de desigualdades) Deve ter também o artigo avulso no site da eureka. tem um raciocínio que ilustra essa desigualdade. Suponha que você tem 3 caixas: uma com notas de $100, outra com notas de $10 e outra com notas de $1. Suponha que você pode pegar 30 de uma caixa, 20 de outra e 7 de outra, mas você pode escolher em qual vc pega 30, em qual vc pega 20, etc. O que vc faz? Bem, é claro que você vai ordenar os dois (100101) e (30207) e pegar 30*100+10*20+7*1... Pegue a soma máxima S entre todas as possiveis somas sum(xi zi). Queremos provar que ij implica z_i=z_j. Suponha que não, temos ij e z_iz_j. Seja S' a soma que você obtém trocando z_i e z_j de lugar. Mostre que S'S, o que será absurdo. Bruno Leite http://www.ime.usp.br/~brleite thanks! fê! _ Converse com seus amigos online, faça o download grátis do MSN Messenger: http://messenger.msn.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
RES: [obm-l] ajuda !!
Correção: No caso de N ser múltiplo de 10, o número de dígito é o valor do logarítmo somado com 1. -Mensagem original- De: Edilon Ribeiro da Silva em nome de Edilon Ribeiro da Silva Enviada: dom 25/8/2002 12:50 Para: [EMAIL PROTECTED] Cc: Assunto: RES: [obm-l] ajuda !! Fernanda, Para sabermos a quantidade de dígitos de um número N (N inteiro maior que ou igual a 1) e não múltiplo de 10, basta pegarmos a parte inteira do logarítmo na base 10 de N e adicionarmos 1. Se N é múltiplo de 10, o número de dígitos é o próprio valor do logarítmo. Seja N = ^ e n o número de dígitos de N. Antes de calcularmos, é interessante perceber que n está entre 3* + 1 e 4* + 1, pois 10^3 10^4. logN = *log() logN = 16210,70787939468 Portanto n = 16210 + 1 = 16211 dígitos. Veja que 1 n 1. Obs: 1) Se esta for uma questão de prova/concurso/olimpíada, onde não é permitido o uso de calculadoras, deveremos proceder da seguinte forma: logN = *log(4*11*101) logN = *(log4 + log11 + log101) logN = *(2*log2 + log11 + log101) Neste caso, deveriam ser dados os valores de log2, log11 e log101 (pois são números primos) com casas decimais suficientes para levar em consideração a grandeza de . 2) Você fala em estimativa ou aproximação de n. Por que aproximar ou estimar, se podemos calcular exatamente? Edilon Ribeiro. winmail.dat Description: application/ms-tnef
Re: [obm-l] Numeros primos - solução
O que significa: " Em tempo polinomial ", como foi citado no texto sobre a fórmula dos matemáticos hindus, para numeros primos Um abraço Crom
[obm-l] Umazinha de Fisica(IME)
Alguem saberia me explicar o fato de alguns cursinhos na resoluçao da questao de dinamica do IME do ano passado(dos 3 blocos)considerarem que o sistema como um todo entrasse em movimento enquanto que na minha concepção o sistema como um todo devesse ficar em repouso embora o blocos de massa m1 e m2 tendessem a se mover um em relaçao ao outro, pois mesmo com a movimentaçao de m1 e m2 a parte direita do sistema por ter massa m1+m2 nao ganharia movimento em relaçao a parte esquerda do sistema de massa M, ja que no enunciado é dito que M=m1+m2. Um abraço,Leonardo _ MSN Photos é a maneira mais fácil e prática de editar e compartilhar sua fotos: http://photos.msn.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] Produto de dois primos
Oi colegas, a lista é para Matemática uma das poucas coisas que se mantém sempre pura. Matemática... e pura. Essa é nossa política! 1)Seja n um número natural tal que nenhum primo pRc(n) ou p=Rc(n) divida n. Provar que n é um primo ou um produto de dois primos. Obrigado! Obs: Rc(n) - Raiz Cúbica de nAproveite melhor a Web. Faça o download GRÁTIS do MSN Explorer : http://explorer.msn.com.br/intl.asp#po
[obm-l] Infinitos
Olá pessoal 1) Demonstrar que existem infinitos primos da forma 4n+3, com n inteiro. Ok!Aproveite melhor a Web. Faça o download GRÁTIS do MSN Explorer : http://explorer.msn.com.br/intl.asp#po
[obm-l] RES: [obm-l] Numeros primos - solução
Caro Crom, --- Existem problemas de decisão bem definidos que não podem ser resolvidos por algoritmos. Podemos, portanto, classificar todos os problemas computacionais em duas categorias: aqueles que podem ser resolvidos por algoritmos e aqueles que não podem. Com os grandes avanços da tecnologia da computação das últimas décadas, é razoável esperar que todos os problemas do primeiro tipo possam ser resolvidos de uma maneira satisfatória. Infelizmente, a prática da computação revela que muitos problemas, apesar de solúveis a princípio, não podem ser resolvidos em qualquer sentido prático por computadores devido às excessiva exigências de tempo. Suponha, por exemplo, que sua tarefa é escalonar a visita de um caixeiro viajante a 10 escritórios regionais. Você recebe um mapa com as 10 cidades e as distâncias em kilômetros e lhe pedem para produzir um intinerário que minimiza a distância total percorrida. Esse é, claramente, o tipo de tarefa em que você utilizaria um computador para resolver. E, de um ponto de vista teórico, o problema é certamente solúvel. Se há n cidades para visitar, o número de itinerários possíveis é finito - para ser presciso (n-1)!. Portanto, pode-se facilmente conceder um algoritmo que sistematicamente examina todos os intinerários a fim de localizar o mais curto. Mas ainda há um mal-estar com relação a esse algoritmo. Há muitas viagens a serem examinadas. Para nosso modesto problema de 10 cidades, teríamos de examinar 9! = 362.880 itinarários. Com alguma paciência, isso pode ser realizado por um computador, mas e se tivéssemos 40 cidades a visitar? O número de itinerários seria agora gigantesco: 39!, o que é mais que 10^45. Mesmo que pudéssemos examinar 10^15 viagens por segundo - um passo que é muito rápido mesmo para o mais poderoso supercomputador existente ou projetado - o tempo exigido para completar esse cálculo seria vários bilhões de ciclo de vida do universo! Evidentemente, o fato de um problema ser solúvel na teoria não imediatamente implica que ele possa ser resolvido de maneira realista na prática. A questão é: quais algoritmos devemos considerar como praticamente viável? Como o exemplo do PROBLEMA DO CAIXEIRO VIAJANTE revela, o parâmetro limitador é o tempo ou número de passos exigidos pelo algoritmo em um entrada. O algoritmo (n-1)! para o problema do caixeiro viajante foi demasiado irreal simplemente por causa do excessivo crescimento exponencial de suas exigências de tempo (é fácil ver que a função (n-1)! cresce ainda mais rápido que 2^n). Em contraste, um algoritmo com uma taxa de crescimento polinomial seria obviamente muito mais atraente. Parece que, a fim de capturar a noção de algotitmo praticamente viável, devemos limitar nossos dispositivos computacionais para somente executar um número de passo que é limitado por um polinômio no comprimento de entrada [daí a importância da descoberta dos cientistas da Computação indianos]. A classe de todas as linguagens polinomialmente decidíveis é denotada por P [P do inglês polinomial] e a classe de todas as linguagens que não pertecem a P é denotada por NP [NP do inglês no-polinomial]. Isso justifica o título do artigo dos cientistas: PRIMES IN P. Em que medida a classe P captura a noção intuitiva de problema satisfatoriamente viável? Com que amplitude se aceita a tese de que algoritmos polinomiais são precisamente ou empiricamente viáveis? É razoável dizer que, embora seja a única proposta séria nessa área, ela pode ser desafiada em vários terrenos. Por exemplo, pode-se argumentar que um algoritmo com exigências de tempo n^100 ou mesmo (10^100)n^2, não é praticamente viável, embora tenha um tempo polinomial. Além disso, um algoritmo com exigências de tempo n^(log(log(n)) pode ser considerado perfeitamente viável na prática, a despeito do fato de que seu crescimento não é limitado por qualquer polinômio. O argumento empírico em defesa de nossa tese é que tais limites extremos de tempo, embora teoricamente possíveis, raramente ocorrem na prática: algoritmos polinomiais, que surgem em práticas computacionais, geralmente têm pequenos expoentes e coeficientes costantes agradáveis, enquanto algoritmos não polinomiais são em geral exponenciais e, portanto, de utlização bastante limitada na prática. De acordo com o documento Primes in P, os autores apresentam um algoritmo que decide se um dado número n é primo ou composto [dei uma lida rápida] com uma complexidade computacional O([log(n)]^6), podendo futuramente chegar a O([log(n)]^3), desde que se prove a conjectura de Bhattacharjee-Pandey. --- Notas: 1) Este texto acima foi, essencialmente, retirado do capítulo 6, seções 6.1 e 6.2, do livro ELEMENTOS DE TEORIA DA COMPUTAÇÃO [Trad. Edson Furmankiewicz] de Harry R. Lewis e
Re: [obm-l] Infinitos
Olá Rubens , Acredito que alguém já demonstrou isto aqui .Geralmente estas provas são por absurdo .Suponha que exista uma quantidade finita de primos desta forma .Considere os primos da forma dada : p1, p2 , p3 , ...,pr e considere o número K = 4p1.p2.p3. pr - 1 = 4(p1.p2.p3...pr -1 ) + 3 . Observe que Kpi e composto e deve ter fatores primos da forma 4s+1 ou 4s+3 , e já que multiplicando fatores da forma 4s+1 teremos fatores da forma 4s+1 , concluímos que K deve ter pelo menos um fator da forma 4s+3 . Isto é um absurdo já que este fator deverá dividir a unidade , ok ? Na verdade existe um teorema geral que diz : Se a e b são inteiros positivos primos entre si , então existe infinitos primos da forma an+b . Não me lembro de quem é este teorema . []´s Carlos Victor At 15:36 25/8/2002 -0300, Rubens Vilhena wrote: Olá pessoal 1) Demonstrar que existem infinitos primos da forma 4n+3, com n inteiro. Ok! Aproveite melhor a Web. Faça o download GRÁTIS do MSN Explorer : http://explorer.msn.com.br/intl.asp#po
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: Área do triângulo
Não é difícil... apenas parece... Dado um triângulo ABC, com medianas AM, BN, CL e baricentro G, prolongue AM até P de modo que GM=MP. Então é fácil ver que o triângulo GPC tem lados iguais a 2/3 das medianas de ABC ( Verifique ! ). Como a área de GMC é S/6, a área de GPC têm área S/3. Daí segue que a área procurada é (9/4)*(S/3)=(3/4)S Agora é bem fácil pensar na construção com régua e compasso, olhando para a construção feita acima. Abraços Villard -Mensagem original- De: Vinicius José Fortuna [EMAIL PROTECTED] Para: [EMAIL PROTECTED] [EMAIL PROTECTED] Data: Sábado, 24 de Agosto de 2002 23:30 Assunto: [obm-l] Re: [obm-l] Re: [obm-l] Re: Área do triângulo Pô, coitado do Renato. Com o atraso que o gerenciador da lista tem para enviar os e-mails acabou tendo um monte de gente corrigindo ele. Bruno, com relação ao teorema que vc citou, ele tem algum nome especial para que eu posso buscá-lo em outras fontes? Uma outra pergunta. Dada as medidas das medianas, é possível construir o triângulo com régua e compasso? Como? Obrigado Vinicius Fortuna - Original Message - From: Bruno F. C. Leite [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, August 24, 2002 9:12 PM Subject: Re: [obm-l] Re: [obm-l] Re: Área do triângulo Oi, Posso estar falando uma besteira feia, mas quando eu estudava geometria plana (há 3 anos) eu acho que tinha um teorema que dizia que dado um triangulo, podemos montar um triângulo com suas medianas e a razão entre as áreas destes triangulos é 3/4. Se isto for verdade, o problema fica fácil. Bruno Leite http://www.ime.usp.br/~brleite At 20:04 24/08/02 -0300, you wrote: Renato, x, y e z são as medianas do triângulo e não seus lados! Um abraço! Eduardo. From: Renato Lira [EMAIL PROTECTED] Para saber se o triangulo realmente existe, tem que obedecer as seguintes regras: x + y z ; x + z y ; y + z x Para saber sua área sabendo somente os lados: seja p o semi perimetro (x+y+z)/2 S = sqrt[p(p-x)(p-z)(p-y)] - Original Message - From: Vinicius José Fortuna [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, August 24, 2002 7:36 PM Subject: [obm-l] Área do triângulo Uma das questões do último campeonato de programação do site de Valladolid (http://acm.uva.es/problemset) era o seguinte: Dados os tamanhos x, y, z das medianas de um triângulo, calcular sua área ou dizer que tal triângulo não existe. Alguém tem alguma idéia de como resolver? Obrigado Vinicius Fortuna IC-Unicamp = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] RES: [obm-l] função
Caro Carlos, Questão 01 item a) Fazendo x = 1 e y = 1 temos: 2*f(1)*f(1) = [f(1+1) + f(1-1)] 2*[f(1)]^2 = f(2) + f(0) Como f(1) = 0, então: f(2) + f(0) = 0 (I) Façamos agora x = 0 e y =0. 2*f(0)*f(0) = [f(0+0) + f(0-0)] 2*[f(0)^2] = 2*f(0) f(0)^2 - f(0) = 0 f(0)*[f(0) - 1] = 0, isso implica f(0) = 0 ou f(0) - 1 = 0. Não podemos usar f(0) = 0, pois, em tendo em vista (I) e a propriedade da função f, a função tornar-se-á identicamente nula, o que é contra o enunciado. Dessa forma temos: f(0) - 1 = 0. Logo, f(0) = 1. Como f(0) = 1, de (I) conclui-se que f(2) = -1. Façamos agora, x = 2 e y = 1. Assim: 2*f(2)*f(1) = [f(2+1) + f(2-1)] 2*f(2)*f(1) = f(3) + f(1) Mas f(1) = 0, então f(3) = 0 Portanto, f(0) = 1, f(2) = -1 e f(3) = 0. Item b) Para mostrarmos que f(x+4) = f(x), basta mostrarmos que f(t+4) = f(t) por meio de mudanças de variáveis. Sejam x = t+3 e y = 1. Dessa forma temos: 2*f(t+3)*f(1) = [f(t+3+1) + f(t+3-1)] 2*f(t+3)*f(1) = f(t+4) + f(t+2) Como f(1) = 0, temos: f(t+4) + f(t+2) = 0 (II) Agora basta fazer x = t+1 e y = 1. 2*f(t+1)*f(1) = [f(t+1+1) + f(t+1-1)] 2*f(t+1)*f(1) = f(t+2) + f(t) Como f(1) = 0, temos: f(t+2) + f(t) = 0 (III) Subtraindo (III) de (II) chega-se a: f(t+4) - f(t) = 0, ou seja, f(t+4) = f(t). Como t é qualquer real, então f(x+4) = f(x). (c.q.m) Edilon Ribeiro. --- -Mensagem original- De: cabs.bentes [mailto:[EMAIL PROTECTED]] Enviada: dom 25/8/2002 14:11 Para: [EMAIL PROTECTED] Cc: Assunto: [obm-l] função Oi pessoal; Será que alguem poderia me ajudar com os seguintes problemas : 1) Seja f:R-R uma função não identicamente nula, tal que f(1)=0 e 2f(x)f(y)=[f(x+y)+f(x-y)] ; para x e y pertencentes a R. a) quais os valores de f(0); f(2); f(3) b) mostre que f(x+4)=f(x) ; para qualquer x E R. 2) Seja f:R-R uma função tal que f(x)=x^2-3x+4. Quantas soluções reais tem a equação f(f(f...f(x)...))=2, onde f é aplicada 2002 vezes ? Obrigado ... Carlos. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] = winmail.dat Description: application/ms-tnef
Re: [obm-l] RES: [obm-l] Numeros primos - solução
Ola, A classe de todas as linguagens polinomialmente decidíveis é denotada por P [P do inglês polinomial] e a classe de todas as linguagens que não pertecem a P é denotada por NP [NP do inglês no-polinomial]. NP vem do ingles nondeterministic polynomial time. Problemas (ou linguagens, como voce definiu) em NP nao sao necessariamente nao-polinomiais. Se fossem, teriamos resposta para o problema P=NP. NP representa a classe de problemas para os quais se consegue um algoritmo nao-deterministico que rode em tempo polinomial (equivalente a se conseguir verificar uma saida deterministicamente em tempo polinomial). Todo problema em P necessariamente esta em NP, mas o inverso ainda eh um problema em aberto. De acordo com o documento Primes in P, os autores apresentam um algoritmo que decide se um dado número n é primo ou composto [dei uma lida rápida] com uma complexidade computacional O([log(n)]^6), podendo futuramente chegar a O([log(n)]^3), desde que se prove a conjectura de Bhattacharjee-Pandey. Talvez minha olhada tenha sido mais rapida que a sua, mas eu havia lido o seguinte: We give a deterministic, O((log n)^12) time algorithm for testing if a number is prime. Heuristically, our algorithm does much better: under a widely believed conjecture on the density of Sophie Germain primes (primes p such that 2p+1 is also prime), the algorithm takes only O((log n)^6) steps. Mas realmente, no final do artigo, seguindo outras conjecturas os autores comentam a possibilidade de uma implementacao O((log n)^3). No entanto, enquanto a Conjectura 5 do artigo (Sophie Germain) ainda nao for provada, o algoritmo deles continua tendo complexidade deterministica O((log n)^12), o que, para numeros com 1000 bits por exemplo, nao eh muito viavel na pratica. Minhas referencias sao dos livros: Introduction to Algorithms. Thomas Cormen et al. Introduction to Algorithms - A creative approach. Udi Manber. e do artigo: PRIMES is in P. Agrawal, Kayal e Saxena. Abracos, Rodrigo = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] ibero
From: Fernanda Medeiros [EMAIL PROTECTED]
olá ,
gostaria de ajuda nestas questões:
1.encontrar o menor nº natural n com a seguinte propriedade: entre
quaisquer
n nºs distintos do conjunto {1,2,...,999} pode-se escolher 4 nºs
diferentes
a,b,c,d tais que a+2b+3c=d
Eu nunca pensei seriamente nessa. Mas sei que faz tempo que ela vem para a
lista e nunca vi uma solução.
2.encontre todos os inteiros positivos q são menores q 1000 e cumprem
a seguinte condição:o cubo da soma dos seus dígitos é igual ao quadrado do
referido inteiro.
valeuz!!
[]´s
fÊ
Essa é uma das questões mais fáceis que eu já vi na Ibero Americana.
O número é n e a soma dos seus dígitos é s. Tem-se
s^3 = n^2.
Pelos fatores primos (não vou fazer essa parte) se vê que
s é um quadrado perfeito e
n é um cubo perfeito.
Pegue os nove cubos perfeitos (1^3, 2^3, 3^3, ..., 9^3) menorees que 1000, e
veja se a soma de seus dígitos é um quadrado perfeito. Aí basta conferir se
s^3 = n^2. Se não me engano a única solução é 3^3 = 81, isso você pode
conferir.
Um abração!
Eduardo.
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é [EMAIL PROTECTED]
=
[obm-l] olimpiada virtual
Ola companheiros da lista Gostaria de fazer uma sugestao. Porque nos nao instituimos uma olimpiada virtual de Matematica, por e-mail. Poderia ser mais ou menos assim: 0-Os parcicipantes se cadastram no inicio do torneio (nome, e-mail, endereco...) 1-Cada participante tem o direito de propor aos demais no maximo 1 questao de Matematica por dia; 2-Cada questao vale 3 pontos e tem 10 dias para ser respondida por quem nao a propos; 3-A primeira solucao correta para um problema da a quem respondeu os 3 pontos da questao; 4-Se faltar um detalhe na questao, quem respondeu primeiro perde 1 ponto (dos 3 que havia ganho) e quem completar a solucao ganha 1 ponto; 5-Se a questao nao for respondida em 10 dias, quem a propos ganha os 3 pontos caso de uma solucao correta para a questao - se precisar de um ajuste quem propos perde um ponto (dos 3 que havia ganho) e quem corrigir ganha 1 ponto; 6-A duracao do torneio pode ser de 1 mes ou 2; So precisamos de 3 coisas: 1-Discutir se as regras vao ser essas mesmas; 2-Professores capazes para julgar as questoes e marcar as pontuacoes; 3-Por a mao na massa - Eric Campos Bastos Guedes [EMAIL PROTECTED] Brasil - RJ - Niteroi Confira o livro: Formulas que geram numeros primos no site www.primeformulas.hpg.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Infinitos
Eh de Dirichlet. Carlos Victor wrote: [EMAIL PROTECTED]"> Ol Rubens , Acredito que algum j demonstrou isto aqui .Geralmente estas provas so por absurdo .Suponha que exista uma quantidade finita de primos desta forma .Considere os primos da forma dada : p1, p2 , p3 , ...,pr e considere o nmero K = 4p1.p2.p3. pr - 1 = 4(p1.p2.p3...pr -1 ) + 3 . Observe que Kpi e composto e deve ter fatores primos da forma 4s+1 ou 4s+3 , e j que multiplicando fatores da forma 4s+1 teremos fatores da forma 4s+1 , conclumos que K deve ter pelo menos um fator da forma 4s+3 . Isto um absurdo j que este fator dever dividir a unidade , ok ? Na verdade existe um teorema geral que diz : Se a e b so inteiros positivos primos entre si , ento existe infinitos primos da forma an+b . No me lembro de quem este teorema . []s Carlos Victor At 15:36 25/8/2002 -0300, Rubens Vilhena wrote: Ol pessoal 1) Demonstrar que existem infinitos primos da forma 4n+3, com n inteiro. Ok! Aproveite melhor a Web. Faa o download GRTIS do MSN Explorer : http://explorer.msn.com.br/intl.asp#po
[obm-l] Re: [obm-l] Duas questões do IME.
Ola Bruno e demais
colegas desta lista...OBM-L,
1) Seja C = { C1, C2, C3, ..., C12 } uma enumeracao dos cavaleiros.
Precisamos determinar o numero de sub-conjuntos de C que tem 5 elementos e
nos quais nao existam dois elementos consecutivos.
Claramente que aqui devemos considerar C1 como consecutivo de C12.
Estas observacoes deixam evidente que trata-se de uma aplicacao imediata do
segundo lema de Kaplanski. Portanto :
g(12,5) = [12/(12-5)]*BINOM(12-5,5) = 36
2)Ao fim de uma partida e atribuido a cada clube que dela participou uma
pontuacao : 1, se ganhou; 1/2, se empatou e 0 se perdeu. A SOMA DOS PONTOS
ATRIBUIDOS E SEMPRE UM !
Isto significa que a soma dos pontos ganhos de todos os clubes e igual ao
numero de partidas disputadas. Ora, se N for a quantidade de clubes que nao
sao do Rio, N+1 e a quantidade de partidas que cada clube disputou. Como ha
N+2 clubes, o total de partidas e :
[(N+2)*(N+1)/2]
O total de pontos e : 8 + N*K. Portanto :
8+N*K = [(N+2)*(N+1)/2]
16+2N*K = N^2 + 3N + 2 = 2NK=N^2 + 3N - 14
2K = (N+3) - 14/N = 14/N = (N+3) - 2K
Qualquer que seja K ( 5/2, 7, etc ), 2K e um inteiro e (N+3) tambem. Logo,
14/N deve ser inteiro. Assim N deve pertencer ao conjunto :
{-14,-7,-2,-1,1,2,7,14}
A - Os numeros negativos sao absurdos, pois N e o numero de clubes do
campeonato que nao sao do Rio.
B - 1 ou 2 sao absurdos pois 8 foi a soma dos pontos ganhos dos clubes do
Rio.
Precisamos decidir, portanto, entre N=7 ou N=14.
N=7
Consistente ! Por que ? Porque teriamos K = 4 e N+2=9 clubes. Cada clube
jogaria 8 partidas. IMAGINE um campeonato nos moldes do enunciado do
problema no qual todos os jogos terminem empatados ...
N=14
Consistente ! Por que ? Porque teriamos K=8 e N+2=16 clubes. Cada clube
jogaria 15 partidas. IMAGINE um campeonato nos moldes do enunciado do
problema no qual cada clube de fora do Rio ganhou 8 partidas e perdeu 7,
um clube do Rio ganhou 8 partidas e perdeu 7 e o outro clube do Rio perdeu
as 15 partidas.
Segue que participaram do torneio 9 ou 16 clubes.
AFIRMACAO : Se um clube participou de um campeonato no qual jogou com cada
participante uma unica vez e ele teve, neste campeonato, D derrotas e E
empates, entao, a QUANTIDADE MAXIMA DE OUTROS CLUBES que podem ter tido uma
pontuacao igual ou superior a dele, independente da premiacao dada a
Vitorias e empates, e 2D+E, desde que este numero nao entre em conflito
com a quantidade de jogos (D+E+V).
A afirmacao acima e Verdadeira ou Falsa ?
Com os melhores votos
de paz profunda, sou
Paulo Santa Rita
1,1951,250802
Olá pessoal da lista,gostaria de uma ajuda nessas duas questões do IME.
1) 12 cavaleiros estão sentados em torno de uma mesa redonda .Cada um dos
doze cavaleiros considera seus dois vizinhos como rivais.Deseja-se formar
um grupo de 5 cavaleiros para libertar uma princesa.Nesse grupo não poderá
haver cavaleiros rivais .Determine de quantas maneiras é possível escolher
esse grupo.
2) Dois clubes do Rio de Janeiro participaram de um campeonato nacional de
futebol de salão onde cada vitória valia 1 ponto,cada empate meio ponto e
cada derrota zero ponto.Sabendo que cada participante enfrentou todos os
outros apenas uma vez,que os clubes do Rio de Janeiro totalizaram,em
conjunto, 8 pontos e que cada um dos outros clubes alcançou a mesma
quantidade k de pontos, determine a quantidade de clubes que participou do
torneio.
Um abraço,
Bruno Moss.
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é [EMAIL PROTECTED]
=
[obm-l] Olimpíada virtual
Ei Eric Foi uma ótima idéia e concordo plenamente com esse torneio cultural Eu tb propus um canal em mIRC, mas ninguém retornou até agora.. Valeu!! Leonardo Borges Avelino
[obm-l] Re: [obm-l] RES: [obm-l] Numeros primos - solução
http://www.umcs.maine.edu/~chaitin/ Esse é o link para a pagina do criador da Algorithm Information Theory, um dos grandes matematicos vivos. Vale a pena dar um olhada : ) abraços - Original Message - From: Edilon Ribeiro da Silva [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Sunday, August 25, 2002 5:13 PM Subject: [obm-l] RES: [obm-l] Numeros primos - solução Caro Crom, --- Existem problemas de decisão bem definidos que não podem ser resolvidos por algoritmos. Podemos, portanto, classificar todos os problemas computacionais em duas categorias: aqueles que podem ser resolvidos por algoritmos e aqueles que não podem. Com os grandes avanços da tecnologia da computação das últimas décadas, é razoável esperar que todos os problemas do primeiro tipo possam ser resolvidos de uma maneira satisfatória. Infelizmente, a prática da computação revela que muitos problemas, apesar de solúveis a princípio, não podem ser resolvidos em qualquer sentido prático por computadores devido às excessiva exigências de tempo. Suponha, por exemplo, que sua tarefa é escalonar a visita de um caixeiro viajante a 10 escritórios regionais. Você recebe um mapa com as 10 cidades e as distâncias em kilômetros e lhe pedem para produzir um intinerário que minimiza a distância total percorrida. Esse é, claramente, o tipo de tarefa em que você utilizaria um computador para resolver. E, de um ponto de vista teórico, o problema é certamente solúvel. Se há n cidades para visitar, o número de itinerários possíveis é finito - para ser presciso (n-1)!. Portanto, pode-se facilmente conceder um algoritmo que sistematicamente examina todos os intinerários a fim de localizar o mais curto. Mas ainda há um mal-estar com relação a esse algoritmo. Há muitas viagens a serem examinadas. Para nosso modesto problema de 10 cidades, teríamos de examinar 9! = 362.880 itinarários. Com alguma paciência, isso pode ser realizado por um computador, mas e se tivéssemos 40 cidades a visitar? O número de itinerários seria agora gigantesco: 39!, o que é mais que 10^45. Mesmo que pudéssemos examinar 10^15 viagens por segundo - um passo que é muito rápido mesmo para o mais poderoso supercomputador existente ou projetado - o tempo exigido para completar esse cálculo seria vários bilhões de ciclo de vida do universo! Evidentemente, o fato de um problema ser solúvel na teoria não imediatamente implica que ele possa ser resolvido de maneira realista na prática. A questão é: quais algoritmos devemos considerar como praticamente viável? Como o exemplo do PROBLEMA DO CAIXEIRO VIAJANTE revela, o parâmetro limitador é o tempo ou número de passos exigidos pelo algoritmo em um entrada. O algoritmo (n-1)! para o problema do caixeiro viajante foi demasiado irreal simplemente por causa do excessivo crescimento exponencial de suas exigências de tempo (é fácil ver que a função (n-1)! cresce ainda mais rápido que 2^n). Em contraste, um algoritmo com uma taxa de crescimento polinomial seria obviamente muito mais atraente. Parece que, a fim de capturar a noção de algotitmo praticamente viável, devemos limitar nossos dispositivos computacionais para somente executar um número de passo que é limitado por um polinômio no comprimento de entrada [daí a importância da descoberta dos cientistas da Computação indianos]. A classe de todas as linguagens polinomialmente decidíveis é denotada por P [P do inglês polinomial] e a classe de todas as linguagens que não pertecem a P é denotada por NP [NP do inglês no-polinomial]. Isso justifica o título do artigo dos cientistas: PRIMES IN P. Em que medida a classe P captura a noção intuitiva de problema satisfatoriamente viável? Com que amplitude se aceita a tese de que algoritmos polinomiais são precisamente ou empiricamente viáveis? É razoável dizer que, embora seja a única proposta séria nessa área, ela pode ser desafiada em vários terrenos. Por exemplo, pode-se argumentar que um algoritmo com exigências de tempo n^100 ou mesmo (10^100)n^2, não é praticamente viável, embora tenha um tempo polinomial. Além disso, um algoritmo com exigências de tempo n^(log(log(n)) pode ser considerado perfeitamente viável na prática, a despeito do fato de que seu crescimento não é limitado por qualquer polinômio. O argumento empírico em defesa de nossa tese é que tais limites extremos de tempo, embora teoricamente possíveis, raramente ocorrem na prática: algoritmos polinomiais, que surgem em práticas computacionais, geralmente têm pequenos expoentes e coeficientes costantes agradáveis, enquanto algoritmos não polinomiais são em geral exponenciais e, portanto, de utlização bastante limitada na prática. De acordo com o documento Primes in P, os autores apresentam um algoritmo que decide se um dado número n é primo ou composto [dei uma lida rápida] com uma complexidade computacional O([log(n)]^6), podendo futuramente chegar a O([log(n)]^3), desde que se
