P versus NP

Por exemplo, se você tem um problema, e alguém diz "A resposta ao seu problema é o conjunto de números 1, 2, 3, 4, 5", um computador pode ser capaz, rapidamente, de descobrir se a resposta está certa ou errada, mas pode levar muito tempo para que o computador chegue a "1, 2, 3, 4, 5" por si só. Outro exemplo inclui encontrar números primos. É fácil verificar se um número é primo, mas é muito difícil encontrar esses números em primeiro lugar. Para algumas perguntas interessantes e práticas deste tipo, nos falta qualquer maneira de encontrar uma resposta rapidamente, mas se nos for dada uma resposta, é possível verificar - isto é, verificar - a resposta rapidamente. Desta forma, os problemas NP podem ser considerados como enigmas: pode ser difícil encontrar a resposta para um enigma, mas uma vez que se ouve a resposta, a resposta parece óbvia. Nesta comparação (analogia), a pergunta básica é: os enigmas são realmente tão difíceis quanto pensamos, ou está faltando algo?

Como estes tipos de questões P versus NP são tão importantes na prática, muitos matemáticos, cientistas e programadores de computador querem provar a proposta geral, que cada problema verificado rapidamente também pode ser resolvido rapidamente. Esta questão é suficientemente importante para que o Clay Mathematical Institute dê $1.000.000 a qualquer um que forneça com sucesso uma prova ou uma explicação válida que a desminta.

Cavando um pouco mais fundo, vemos que todos os problemas P são problemas NP: é fácil verificar se uma solução está correta, resolvendo o problema e comparando as duas soluções. Entretanto, as pessoas querem saber o oposto: Existem outros problemas NP além dos problemas P, ou todos os problemas NP são apenas problemas P? Se os problemas NP não são realmente os mesmos que os problemas P (P ≠ NP), isso significaria que nenhuma maneira geral e rápida de resolver esses problemas NP pode existir, não importa o quão difícil pareça. Entretanto, se todos os problemas NP são problemas P (P = NP), isso significaria que existem novos métodos muito rápidos de solução de problemas. Simplesmente ainda não os encontramos.

Como os melhores esforços dos cientistas e matemáticos ainda não encontraram métodos gerais e fáceis para resolver problemas NP, muitas pessoas acreditam que existem outros problemas NP além dos problemas P (ou seja, que P ≠ NP é verdade). A maioria dos matemáticos também acredita que isso seja verdade, mas atualmente ninguém provou isso através de uma análise matemática rigorosa. Se for possível provar que NP e P são a mesma coisa (P = NP é verdade), isso teria um enorme impacto em muitos aspectos da vida cotidiana. Por esta razão, a questão de P versus NP é um tópico importante e amplamente estudado.

Suponha que alguém queira construir duas torres, empilhando rochas de massa diferente. Uma quer ter certeza de que cada uma das torres tem exatamente a mesma massa. Isso significa que alguém terá que colocar as rochas em duas pilhas que tenham a mesma massa. Se se adivinhar uma divisão das rochas que se pensa que funcionará, seria fácil para se verificar se a pessoa estava certa. (Para verificar a resposta, pode-se dividir as rochas em duas pilhas, depois usar um equilíbrio para ver se elas têm a mesma massa). Porque é fácil verificar este problema, chamado 'Partição' pelos cientistas da computação - mais fácil do que resolvê-lo completamente, como veremos - não é um problema P. ^[]

Quão difícil é resolver, de forma direta? Se se começa com apenas 100 pedras, há 2^{100-1}-1 = 633.825.300.114.114.700.748.351.602.687, ou cerca de 6,3 x 10^{29} formas (combinações) possíveis de dividir estas pedras em duas pilhas. Se se pudesse verificar uma combinação única de rochas todos os dias, seriam necessários 1,3 x 10^{22} ou 1.300.000.000.000.000.000.000.000 anos de esforço. Para comparação, os físicos acreditam que o universo tem cerca de 1,4 x 10^{10} anos (450.000.000.000.000.000.000.000 ou cerca de 4,5 x 10^{17} segundos, ou cerca de um trilhão de idade como o tempo que levaria para o nosso esforço de empilhamento de rochas. Isso significa que, se se tomar todo o tempo que passou desde o início do universo, seria necessário verificar mais de dois trilhões (2.000.000.000.000.000) de maneiras diferentes de dividir as rochas a cada segundo, a fim de verificar todas as maneiras diferentes.

Se alguém programou um computador potente, para testar todas estas formas de dividir as rochas, poderia ser capaz de verificar 1 , 000 , 000 {\i1} combinações por segundo usando os sistemas atuais. Isto significa que ainda seriam necessários 2 , 000 , 000 computadores muito poderosos, trabalhando desde a origem do universo, para testar todas as formas de dividir as rochas.

Entretanto, pode ser possível encontrar um método de dividir as rochas em duas pilhas iguais sem verificar todas as combinações. A pergunta "P é igual a NP?" é uma abreviação para perguntar se algum método como esse pode existir.

Há muitos problemas NP importantes que as pessoas não sabem como resolver de uma forma que seja mais rápida do que testar todas as respostas possíveis. Aqui estão alguns exemplos:

• Um vendedor ambulante quer visitar 100 cidades dirigindo, começando e terminando sua viagem em casa. Ele tem um suprimento limitado de gasolina, de modo que ele só pode dirigir um total de 10.000 quilômetros. Ele quer saber se ele pode visitar todas as cidades sem ficar sem gasolina.
• Uma escola oferece 100 classes diferentes, e um professor precisa escolher uma hora para o exame final de cada classe. Para evitar trapaças, todos os alunos que fazem uma aula devem fazer o exame para aquela aula ao mesmo tempo. Se um aluno faz mais de uma aula, então todos esses exames devem ser realizados em um horário diferente. O professor quer saber se ele pode agendar todos os exames no mesmo dia para que cada aluno possa fazer o exame para cada uma de suas aulas.
• Um agricultor quer levar 100 melancias de diferentes massas para o mercado. Ela precisa embalar as melancias em caixas. Cada caixa só pode conter 20 quilos sem quebrar. O agricultor precisa saber se 10 caixas serão suficientes para que ela leve todas as 100 melancias para o mercado. (Isto é trivial, se não mais de uma melancia pesa mais de 2 kg então qualquer 10 podem ser colocadas em cada uma das caixas, se não mais de dez melancias pesam mais de 2 kg então uma de cada uma delas pode ser colocada em cada caixa, etc., para uma solução rápida; a observação será a chave para qualquer solução rápida como esta ou o problema do conjunto de números).
• Uma grande galeria de arte tem muitas salas, e cada parede é coberta com muitas pinturas caras. O proprietário da galeria quer comprar câmeras para ver estas pinturas, no caso de um ladrão tentar roubar alguma delas. Ele quer saber se 100 câmeras serão suficientes para ele ter certeza de que cada quadro possa ser visto por pelo menos uma câmera.
• O problema do clique: O diretor de uma escola tem uma lista de quais alunos são amigos uns dos outros. Ela quer encontrar um grupo de 10% dos alunos que são todos amigos uns dos outros.

No exemplo acima, vemos que com 100 rochas, há 2 100 maneiras de dividir o conjunto de rochas. Com n rochas estilo n, há 2 n combinações estilo 2 ^n. A função f ( n ) = 2 n {\i1}f(n)=2 ^{n}} é uma função exponencial. É importante para NP porque modela o pior número de cálculos que são necessários para resolver um problema e, portanto, a pior quantidade de tempo necessária.

 Para qualquer problema em particular, as pessoas encontraram maneiras de reduzir o número de cálculos necessários. Pode-se descobrir que uma maneira de fazer apenas 1% do pior número de cálculos e que economiza muito em computação, mas isso ainda é 0,01 × ( 2 n ) {\i1} 0,01 vezes (2^{n}) os cálculos. E cada rocha extra ainda duplica o número de cálculos necessários para resolver o problema. Há percepções que podem produzir métodos para fazer ainda menos cálculos produzindo variações do modelo: por exemplo, 2 n / n 3 ^{\i}/n^{3}}. . Mas a função exponencial ainda domina à medida que n {\i1} cresce o estilo de jogo n

Considere o problema de agendamento de exames (descrito acima). Mas suponha, a seguir, que haja 15.000 alunos. Há um programa de computador que leva os horários de todos os 15.000 alunos. Ele funciona em uma hora e produz uma programação de exames para que todos os alunos possam fazer seus exames em uma semana. Ele satisfaz muitas regras (sem exames back-to-back, não mais que 2 exames em qualquer período de 28 horas, ...) para limitar o estresse da semana de exames. O programa funciona por uma hora no intervalo intermediário e todos conhecem sua agenda de exames com muito tempo para se preparar.

No ano seguinte, no entanto, há mais 10 alunos. Se o mesmo programa for executado no mesmo computador, então essa hora vai se transformar em 2 10 ^{10} horas, porque cada estudante adicional dobra os cálculos. São 6 ^6 semanas no estilo de exibição! Se houvesse mais 20 alunos, então

2 20 horas = 1048576 horas ~ 43691 dias ~ 113 anos

Assim, para 15.000 alunos no estilo "15.000", leva uma hora. Para 15020 estudantes, leva 113 anos.

Como você pode ver, as funções exponenciais crescem muito rápido. A maioria dos matemáticos acredita que os problemas NP mais difíceis requerem um tempo exponencial para serem resolvidos.

Os matemáticos podem mostrar que existem alguns problemas NP que são NP-Complete. Um problema NP-Completo é pelo menos tão difícil de resolver quanto qualquer outro problema NP. Isto significa que se alguém encontrasse um método para resolver qualquer problema NP-Completo rapidamente, poderia usar esse mesmo método para resolver todos os problemas NP rapidamente. Todos os problemas listados acima são NP-Complete, portanto se o vendedor encontrasse uma maneira de planejar sua viagem rapidamente, ele poderia dizer ao professor, e ela poderia usar esse mesmo método para agendar os exames. O fazendeiro poderia usar o mesmo método para determinar quantas caixas ela precisa, e a mulher poderia usar o mesmo método para encontrar uma maneira de construir suas torres.

Como um método que resolve rapidamente um desses problemas pode resolver todos eles, há muitas pessoas que querem encontrar um. Entretanto, como há tantos problemas NP-Complete diferentes e ninguém até agora encontrou uma maneira de resolver até mesmo um deles rapidamente, a maioria dos especialistas acredita que não é possível resolver os problemas NP-Complete rapidamente.

Propriedades básicas

Na teoria da complexidade computacional, a classe de complexidade NP-complete (abreviada NP-C ou NPC), é uma classe de problemas com duas propriedades:

• Está no conjunto de problemas NP (tempo polinomial não-determinístico): Qualquer solução dada para o problema pode ser verificada rapidamente (em tempo polinomial).
• Está também no conjunto de problemas NP-duros: Aqueles que são pelo menos tão difíceis quanto os problemas mais difíceis na PN. Os problemas que são NP-duros não precisam ser elementos do NP; de fato, eles podem até mesmo não ser decidíveis.

Visão formal

NP-complete é um subconjunto de NP, o conjunto de todos os problemas de decisão cujas soluções podem ser verificadas em tempo polinomial; NP pode ser definido de forma equivalente como o conjunto de problemas de decisão resolvidos em tempo polinomial em uma máquina. Um problema p em NP também está em NPC se e somente se todo outro problema em NP for transformado em p em tempo polinomial. NP-completo era para ser usado como adjetivo: os problemas na classe NP-completo eram como NP+problemas completos.

Os problemas NP completos são estudados porque a capacidade de verificar rapidamente soluções para um problema (NP) parece estar correlacionada com a capacidade de resolver rapidamente o problema (P). É encontrado todo problema no NP é rapidamente resolvido - como chamado de P = NP: conjunto de problemas. O único problema em NP-completo é resolvido rapidamente, mais rápido que cada problema em NP também é rapidamente resolvido, porque a definição de um problema em NP-completo afirma que cada problema em NP deve ser rapidamente redutível a cada problema em NP-completo (ele é reduzido no tempo polinomial). [1]

Exemplos

O problema de satisfação booleana é conhecido por ser NP completo. Em 1972, Richard Karp formulou 21 problemas que são conhecidos por serem NP completos. Estes são conhecidos como os 21 problemas NP-completos de Karp. Eles incluem problemas como o problema de programação Inteiro, que aplica técnicas de programação linear aos inteiros, o problema da mochila, ou o problema da cobertura do vértice.