11 min de leitura
Atualizado em
Redução de polinômio: como reduzir e o que é na computação
Redução de polinômio é a simplificação de uma expressão algébrica pela soma e subtração de seus termos semelhantes, aqueles com a mesma parte literal. Na computação, o termo nomeia outra ideia, a redução polinomial (Y ≤P X), usada para comparar a dificuldade de problemas em P, NP e NP-completo.

A expressão aparece em dois contextos bem diferentes. Na matemática escolar, reduzir um polinômio é deixar a expressão mais curta. Na ciência da computação, redução é a transformação de um problema em outro em tempo polinomial. A seguir estão os dois significados, com mais espaço para a álgebra, que é o que a maioria dos estudantes procura, e um resumo objetivo da teoria da complexidade. Para revisar o restante da matéria, consulte o guia completo de Matemática para o ENEM e vestibulares.
Índice
O que é redução de polinômio na álgebra?
Quais são os tipos de polinômio pela quantidade de termos?
Como reduzir um polinômio passo a passo?
Como calcular o grau de um polinômio?
O que é redução polinomial na complexidade computacional?
Quais são as classes P, NP, co-NP, NP-difícil e NP-completo?
Como provar que um problema é NP-completo?
Quais reduções clássicas aparecem em provas?
Quais exceções e limites da prática cobram em provas?
Como estudar redução de polinômio para concursos?
O que é redução de polinômio na álgebra?
Um monômio é uma expressão algébrica com um único termo, como 15x³, 6x² ou -9x. Ele tem um coeficiente (a parte numérica, como o 15) e uma parte literal (as letras com seus expoentes, como x³). O termo sem letra, como o -12 em 15x³ + 6x² - 9x - 12, é o termo independente. Já o polinômio é a soma ou a subtração de um número finito de monômios.
Reduzir um polinômio é juntar os termos semelhantes, isto é, os monômios com a mesma parte literal (mesmas letras com os mesmos expoentes). Os coeficientes desses termos são somados ou subtraídos e a parte literal é mantida. Termos que não são semelhantes continuam separados. Um polinômio reduzido fica pronto para aplicar produtos notáveis e fatoração.
Quais são os tipos de polinômio pela quantidade de termos?
Os nomes dependem do número de termos depois da redução. Por isso, reduza antes de nomear: 5a³b² - 9a³b² parece um binômio, mas os dois termos são semelhantes e se juntam em -4a³b², que é um monômio.
Nome | Termos (já reduzido) | Exemplo |
|---|---|---|
Monômio | 1 | 9a²x |
Binômio | 2 | 3x + 2y |
Trinômio | 3 | x² + 2x + 1 |
Polinômio | 4 ou mais | 15x³ + 6x² - 9x - 12 |
Como reduzir um polinômio passo a passo?
Elimine os parênteses. Sinal de mais antes dos parênteses mantém os sinais de dentro. Sinal de menos inverte todos eles: -(2x - 3) = -2x + 3.
Identifique os termos semelhantes observando a parte literal de cada monômio.
Agrupe os termos semelhantes, deixando-os lado a lado.
Opere os coeficientes e repita a parte literal. Termos opostos se anulam.
Exemplo 1: reduzir 12x² - 10x + 4 - 6x² + 14x - x. Os termos semelhantes são 12x² e -6x², de um lado, e -10x, +14x e -x, do outro (o coeficiente de -x é -1). Operando, (12 - 6)x² = 6x² e (-10 + 14 - 1)x = 3x. O polinômio reduzido é 6x² + 3x + 4.
Exemplo 2: reduzir (2x · 4yx) + 5xy - x + (25x : 5). Primeiro resolvem-se as operações entre parênteses: 2x · 4yx = 8x²y e 25x : 5 = 5x. A expressão vira 8x²y + 5xy - x + 5x. Como -x + 5x = 4x, o resultado é 8x²y + 5xy + 4x.
Exemplo 3: reduzir 5x² + 3x - 2x² + 4 - 3x + 6. Os termos em x² dão 3x², os termos +3x e -3x se anulam e 4 + 6 = 10. A forma reduzida é 3x² + 10.
Um erro comum aparece em afirmações como esta:
"Em 4x² + 3x, posso somar os dois termos e obter 7x³."
A afirmação está errada. Os termos 4x² e 3x têm partes literais diferentes, portanto não são semelhantes e não se somam. Na adição, aliás, os expoentes nunca são somados: eles só são mantidos quando os termos são semelhantes. O polinômio 4x² + 3x já está reduzido.
Como calcular o grau de um polinômio?
O grau de um polinômio reduzido depende de quantas variáveis ele tem:
Uma só variável: o grau é o maior expoente. Em x⁴ + 2x² - 9x + 1, o grau é 4.
Várias variáveis: some os expoentes de cada monômio e fique com o maior resultado. Em AB⁷ + X³Y² + XY⁷ + X²Y⁸, os graus dos monômios são 8, 5, 8 e 10, então o grau do polinômio é 10.
Reduza sempre antes de calcular o grau, porque termos que se anulam podem eliminar o maior expoente. Polinômios de grau 2, como ax² + bx + c, dão origem à equação do 2º grau.
O que é redução polinomial na complexidade computacional?
Na Teoria da Complexidade, uma redução polinomial transforma instâncias de um problema Y em instâncias de um problema X em tempo polinomial. Escreve-se Y ≤P X, lido como "Y é polinomialmente redutível a X". A ideia é que Y não é mais difícil que X: se X fosse resolvido em tempo polinomial, Y também seria. Quando Y ≤P X, o problema X é pelo menos tão difícil quanto Y.
A redução é transitiva: se Y ≤P X e X ≤P Z, então Y ≤P Z. Existem dois tipos principais. Na redução de Karp (many-one), o problema original faz uma única chamada ao problema alvo, e uma instância é "SIM" se, e somente se, a instância transformada também for "SIM". Na redução de Turing (ou de Cook), o algoritmo pode chamar o problema alvo várias vezes, como uma sub-rotina. A de Karp é a mais usada para definir NP-completude. O tema se liga ao estudo de algoritmos e lógica de programação.
Quais são as classes P, NP, co-NP, NP-difícil e NP-completo?
A teoria trabalha com problemas de decisão, que têm resposta SIM ou NÃO. Um certificado é a evidência de que a resposta de uma instância é SIM. No ciclo hamiltoniano, por exemplo, o certificado é a sequência de vértices do ciclo, e conferir se ela é válida leva tempo polinomial.
P: problemas de decisão resolvidos por um algoritmo determinístico em tempo polinomial, como ordenação e caminhos mínimos em grafos.
NP: problemas cujo certificado pode ser verificado em tempo polinomial. Vale P ⊆ NP.
co-NP: problemas cujas respostas NÃO podem ser verificadas em tempo polinomial, ou seja, cujo complemento está em NP. Decidir se um número é composto está em NP (o certificado é um fator), então a primalidade está em co-NP e, desde 2002, também se sabe que está em P.
NP-difícil: um problema X é NP-difícil se todo problema de NP se reduz polinomialmente a X. Ele não precisa estar em NP, e problemas de otimização costumam cair aqui.
NP-completo: problema que está em NP e é NP-difícil. São os mais difíceis de NP, e resolver um deles em tempo polinomial provaria que P = NP.
O que é o problema P = NP?
A pergunta é se todo problema com solução verificável em tempo polinomial também pode ser resolvido em tempo polinomial. É um dos sete Problemas do Milênio do Clay Mathematics Institute, com prêmio de 1 milhão de dólares, e segue em aberto. A maioria dos pesquisadores acredita que P ≠ NP. Se P = NP, áreas como inteligência artificial, otimização e criptografia simétrica e assimétrica, que se apoia na dificuldade de certos problemas, seriam profundamente afetadas.
Como provar que um problema é NP-completo?
Para mostrar que um problema Π' é NP-completo, siga estes passos:
Prove que Π' está em NP, mostrando que um certificado é verificado em tempo polinomial.
Escolha um problema Π que já seja NP-completo.
Construa uma transformação T que leve qualquer instância de Π a uma instância de Π'.
Prove que T executa em tempo polinomial.
Prove que a instância de Π é "SIM" se, e somente se, a instância transformada de Π' for "SIM".
O erro mais comum de prova está no sentido da redução, como nesta frase:
"Para provar que X é NP-completo, reduzo X a um problema NP-completo conhecido."
A afirmação está errada, porque o sentido está invertido. Reduz-se o problema NP-completo já conhecido ao problema novo (Π ≤P Π'), pois só assim o novo problema herda a dificuldade.
O primeiro problema NP-completo foi a satisfatibilidade, na forma do CIRCUIT-SAT, demonstrada por Stephen Cook em 1971 e, de modo independente, por Leonid Levin em 1973 (teorema de Cook-Levin). A prova mostra que qualquer algoritmo que verifique certificados em tempo polinomial pode ser simulado por um circuito lógico. A partir daí, cada novo problema entra na lista por redução.
Quais reduções clássicas aparecem em provas?
Redução | Ideia da construção |
|---|---|
CIRCUIT-SAT ≤P SAT | Cada fio do circuito vira uma variável e cada porta vira uma cláusula; a saída final deve ser verdadeira. |
SAT ≤P 3-CNF-SAT | Variáveis auxiliares quebram ou completam as cláusulas até que todas tenham exatamente 3 literais. |
3-CNF-SAT ≤P CLIQUE | Um vértice por literal; arestas entre cláusulas diferentes e literais não complementares; k = número de cláusulas. |
CLIQUE ≤P VERTEX COVER | Usa o grafo complementar: clique de tamanho k em G corresponde a cobertura de tamanho |V| - k em G'. |
VERTEX COVER ≤P INDEPENDENT SET | S é independente se, e somente se, V \ S é uma cobertura de vértices. |
VERTEX COVER ≤P SET COVER | O universo são as arestas e cada vértice gera o conjunto das arestas que o tocam. |
HAM-CYCLE ≤P TSP | Grafo completo com custo 0 nas arestas existentes e 1 nas ausentes; limite k = 0. |
Outras reduções conhecidas são 3-CNF-SAT ≤P SUBSET-SUM, que usa números em base grande em que cada dígito representa uma variável ou uma cláusula, e VERTEX COVER ≤P HAM-CYCLE, que usa subgrafos chamados widgets. Em 1972, Richard Karp listou 21 problemas NP-completos, entre eles clique, cobertura de vértices, coloração de grafos, mochila e partição.
Quais exceções e limites da prática cobram em provas?
Pequenas variações de um problema NP-completo podem mudar a classe dele. Os exemplos mais cobrados são:
2-SAT: cada cláusula tem no máximo 2 literais e o problema está em P, ao contrário do 3-CNF-SAT.
MAX-2-SAT: decidir se é possível satisfazer pelo menos k cláusulas de uma fórmula 2-SAT é NP-completo.
Caminho hamiltoniano em grafos orientados acíclicos: pode ser resolvido em tempo polinomial, embora o caso geral seja NP-completo.
As reduções também são ferramentas de classificação, e não algoritmos práticos. A instância transformada pode ficar bem maior e perder a estrutura do problema original, e muitas vezes já existe um algoritmo direto mais eficiente.
Como estudar redução de polinômio para concursos?
Na álgebra, treine reconhecer termos semelhantes, respeitar os sinais e calcular o grau. Na computação, memorize que P ⊆ NP, que NP-completo é a interseção de NP com NP-difícil, que a redução vai do problema conhecido para o novo e que ela é transitiva. Revise também as exceções 2-SAT e MAX-2-SAT.
Pratique com as questões gratuitas de Matemática, consulte o material de apoio para concursos e organize os estudos na plataforma de estudos do Volitivo.
Referências Bibliográficas
Clay Mathematics Institute: problema P vs NP, enunciado oficial do Problema do Milênio.
Perguntas Frequentes sobre Redução de Polinômio
Qual é a forma reduzida de um polinômio?
É a expressão em que não há mais termos semelhantes. Em 5x² + 3x - 2x² + 4 - 3x + 6, a forma reduzida é 3x² + 10.
Como simplificar polinômios?
Elimine os parênteses, junte os termos semelhantes e opere os coeficientes, mantendo a parte literal.
O problema P = NP já foi resolvido?
Não. Segue como questão em aberto, e a maioria dos pesquisadores acredita que P ≠ NP.
Qual a diferença entre NP-completo e NP-difícil?
Um problema NP-difícil é pelo menos tão difícil quanto todo problema de NP e pode estar fora de NP. Um problema NP-completo é NP-difícil e também pertence a NP.
O que é um certificado em NP?
É a evidência de uma resposta SIM que pode ser verificada em tempo polinomial, como a sequência de vértices de um ciclo hamiltoniano.