Pular para o conteúdo
Todo o material de apoio

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.

Redução de polinômio: à esquerda, a expressão 12x² - 10x + 4 - 6x² + 14x - x reduzida a 6x² + 3x + 4 pela junção de termos semelhantes; à direita, o diagrama das classes P, NP e NP-completo com uma seta de redução polinomial Y ≤P X.

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?

O que é o problema P = NP?

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?

  1. 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.

  2. Identifique os termos semelhantes observando a parte literal de cada monômio.

  3. Agrupe os termos semelhantes, deixando-os lado a lado.

  4. 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:

  1. Prove que Π' está em NP, mostrando que um certificado é verificado em tempo polinomial.

  2. Escolha um problema Π que já seja NP-completo.

  3. Construa uma transformação T que leve qualquer instância de Π a uma instância de Π'.

  4. Prove que T executa em tempo polinomial.

  5. 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.