Quais seriam as implicações do mundo real de uma prova construtiva de

56

Eu tenho um entendimento de alto nível do problema e entendo que, se fosse absolutamente "comprovado" ser verdadeiro com uma solução fornecida, isso abriria a porta para a solução de vários problemas no campo da ciência da computação.P=NP

Minha pergunta é: se alguém publicasse uma prova construtiva e indiscutível de , quais são alguns dos efeitos imediatos que veríamos dessa descoberta? P=NP

Não estou pedindo opiniões opinativas sobre como o mundo seria em 5 a 10 anos. Em vez disso, entendo que esse é um problema fundamentalmente insolúvel que pode mudar radicalmente a maneira como computamos ... muitas coisas (sim, é aqui que minha ignorância está mostrando ...) que não podemos calcular facilmente hoje .

Que tipo de efeito quase imediato teria uma prova completa, precisa e construtiva de no mundo prático?P=NP

RLH
fonte
5
Na pior das hipóteses, pode não haver efeitos práticos (exceto os autores se tornarem famosos) - se a prova não for construtiva, o que significa que alguém prova apenas que existe det. algoritmos pol-time para os problemas NP-completos sem realmente fornecer um.
lukas.coenig
2
Minha coisa favorita a considerar nesse cenário hipotético é o fato de que a otimização se torna fácil. Um caso específico seria que encontrar parâmetros que sejam MLEs globais para qualquer modelo probabilístico se tornaria trivial. Por exemplo, isso afetaria imediatamente os pesquisadores de genética e outras ciências, permitindo-lhes estimar melhor os parâmetros subjacentes a seus modelos.
Nicholas Mancuso
Vale mencionar o que eu esperaria ser a alternativa mais provável no cenário improvável de P = NP: a saber, é encontrada uma prova de que nenhum problema no NP pode falhar em P, mas sem nenhum exemplo de algoritmo P para um NP- problema completo. Só porque alguém pode demonstrar que deve existir alguma solução em P não significa que podemos realmente encontrar essa solução nem verificar sua correção. Ironicamente, essa última parte pode ser mais fácil de fazer se um algoritmo de P para um problema NPC existia, mas bem, isso é um pouco de um problema da galinha e do ovo ...
Eamon Nerbonne
5
O bit "construtivo" é um arenque vermelho. Existe um programa específico bem conhecido que resolve o SAT em tempo polinomial, se (essencialmente ele cai em todos os solucionadores do SAT). Assim, uma prova clássica de P = N P já garante que esse solucionador SAT em particular esteja em P , portanto, também obtemos uma prova construtiva. P=NPP=NPP
21315 Andrej Bauer

Respostas:

34

As pessoas deram boas respostas assumindo que com alguma constante realmente grande. Vou jogar com o otimista e supor que encontramos uma prova de P = N P com uma constante muito pequena. Talvez não seja provável, mas eu vou tentar dar algumas dicas sobre que tipo de coisas que aconteceria se pudéssemos resolver de forma eficiente todos os N P problemas.P=NPP=NPNP

  • Compiladores: alguns programas de computador ficariam um pouco mais rápidos, uma vez que os compiladores usam a coloração gráfica para alocação de registros. Poderíamos alocar exatamente para um grande número de registros. Os compiladores existentes que usam uma solução aproximada (como gráficos de acordes) obteriam melhores resultados e aqueles que usassem uma solução exata seriam mais rápidos.

  • Localização da instalação: as empresas poderiam encontrar o local ideal para instalar fábricas e abastecer depósitos para transportar para suas lojas, quando houver possivelmente milhares de lojas e fábricas. Provavelmente não seria uma grande melhoria em relação às aproximações modernas, mas reduziria os custos.

  • Compra de passagens de avião: as passagens aéreas são estranhas, pois não seguem a igualdade dos triângulos. Às vezes, é mais barato voar de A -> B -> C do que diretamente de A -> C, algo que não aparece ao modelar distâncias. Seria fácil criar um site que encontre a sequência absolutamente mais barata de voos que visitam algumas cidades e começa e termina na sua cidade natal.

  • Projeto de circuitos: circuitos elétricos em um chip são basicamente fórmulas booleanas. Coisas como minimização podem ser calculadas com eficiência, para que nosso hardware fique um pouco mais eficiente.

  • Agendamento: louco por sua escola fazer dois exames ao mesmo tempo? Se sua escola puder quantos horários eles precisam, para que nenhum aluno tenha um conflito, ou com um número de horários, minimize o número de conflitos.P=NP

Esta é apenas uma amostra das aplicações práticas que veríamos se -completeness não eram uma barreira. Tenho certeza de que perdi muitos, mas se a construção em questão tivesse uma boa constante, as implicações seriam de grande alcance.NP

jmite
fonte
5
Citação da Wikipedia em P vs NP : If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found.Estou ciente de que isso pode não se referir às aplicações práticas, mas definitivamente parece um exagero se eu compará-lo à sua resposta. Do que ele está realmente falando?
Nik Kyriakides
4
@ Nicolas Bit de hipérbole, mas eu posso ver o ponto. Para ser incrivelmente impreciso: problemas NPsignificam que podemos verificar se uma solução está correta no tempo polinomial, mas um problema Psignifica que podemos encontrar uma solução no tempo polinomial. Se NP=Pisso significa, é o mesmo esforço para verificar se uma solução está correta ou para encontrar uma solução. Isso ignora completamente os fatores constantes, que fazem uma grande diferença na realidade, obviamente.
Voo
2
Você pode mencionar os efeitos para aplicativos criptográficos?
Dec-- 31/12
5
Se P = NP, as fatorações primas seriam computáveis ​​em tempo polinomial (a fatoração primária é verificável em tempo polinomial). Muitos algoritmos criptográficos - como o RSA incrivelmente comum - dependem da dificuldade de calcular fatorações primárias. Se a "constante" mencionada acima for pequena o suficiente, todas as criptografias de RSA, independentemente do tamanho da chave, poderão ficar sem valor instantaneamente.
precisa saber é o seguinte
3
Você enfatiza que está falando de P = NP "com uma constante muito pequena" e equipara isso a "poderíamos resolver com eficiência todos os problemas de PN". Se sua noção de eficiência inclui constantes tratávelmente pequenas, o teorema da hierarquia de tempo já torna isso impossível: existem problemas que podem ser resolvidos no tempo que não podem ser resolvidos em n 99 , muito menos n 2 ou n log n . n100n99n2nlogn
precisa saber é o seguinte
30

Não veremos necessariamente nenhum efeito. Suponha que alguém encontre um algoritmo que resolva 3SAT em variáveis ​​em 2 100 n operações básicas. Você não poderá executar esse algoritmo em nenhuma instância, pois leva muito tempo. Ou suponha que ela encontre um algoritmo em execução em n 100 operações básicas. Só poderemos usá-lo em instâncias 3SAT em uma única variável, pois, para mais variáveis, leva muito tempo.n2100nn100

Por outro lado, suponha que P NP e que mesmo a hipótese de tempo exponencial mais forte seja válida. Então, em geral, o 3SAT deve ser intratável. No entanto, os solucionadores de SAT parecem estar indo bem em certos problemas.

O que está acontecendo aqui? Existem vários problemas com a pergunta P vs. NP:

  1. Diz respeito apenas ao pior caso.
  2. É apenas assintótico.
  3. Todos os limites de tempo polinomiais são iguais.

Esses problemas lançam dúvidas sobre sua relevância para o mundo real. Agora pode acontecer que algum algoritmo realmente rápido seja encontrado para o 3SAT, tão rápido que até a criptografia simétrica se tornaria quebrável. Mas considero isso altamente improvável. Por outro lado, é perfeitamente consistente que P seja diferente de NP e considere prático; isso quebraria certos esquemas de criptografia de chave pública. Esta é uma situação provável que teria repercussões, mas não está relacionada à questão P vs. NP.

A questão P vs. NP pode ser natural do ponto de vista matemático, mas, na minha opinião, sua relevância prática é duvidosa. A pesquisa sobre a questão, por outro lado, pode ou não ter repercussões práticas; não é guiado por esse aspecto.

Yuval Filmus
fonte
2
Uma prova pode não incluir um algoritmo P para um problema de NPC, mas se isso resultasse na prática, subitamente vale a pena procurar os problemas específicos de NP (ou melhor, agora os problemas de P) que têm valor em larga escala e também constantes tratáveis. Atualmente, ser NP-completo tende a significar que provavelmente não vale a pena o trabalho de olhar. Portanto, a conseqüência prática do mundo real dependeria de como NP é mostrado como P - você esperaria uma prova que permita a construção de um algoritmo P para um problema de NPC, e tudo depende dos detalhes desse algoritmo.
Eamon Nerbonne
Se você tiver 2 ^ 100n resolvido para a 3SAT, ficarei feliz em embarcar na ASIC e ameaçar quebrar o RSA-2048 em tempo suficiente para fazer com que as raízes de 30 anos sejam uma má idéia.
21717 Joshua
17

Uma leitura muito boa aqui é [1], onde Impagliazzo considera cinco possíveis "mundos" onde as relações entre classes de complexidade são diferentes. Por exemplo, em um mundo chamado Algoritmica (consulte a Seção 2.1), temos (ou algum outro "equivalente moral" válido, como N P B P P ).P=NPNPBPP

Na Algoritmica, praticamente qualquer problema de otimização seria trivial. Linguagens de programação podem ser linguagens onde uma espécie as propriedades que uma saída desejada deve ter em relação à entrada, em vez de especificar como a computação deve ser realizada. Os computadores também podem encontrar provas para qualquer teorema no tempo, aproximadamente a duração da prova. (Este ponto de vista é muito optimistas de curso, e depende de um algoritmo eficiente para algumas problema -completo).NP


[1] Russell Impagliazzo. Uma visão pessoal da complexidade dos casos médios. Conferência da Complexidade, 1995.

Juho
fonte
Outra boa leitura anterior é o problema de Steve P versus NP, escrito para o Clay Math Institute.
Kaveh
11

Mesmo sem P = NP, os computadores atuais são incrivelmente poderosos.


Edit 22 Jan 2018 Descobri agora como deveria ter "interpretado" o texto citado no exemplo abaixo. Foi minha culpa, era necessário que o elemento inverso fosse único . Aqui está o meu arquivo de entrada de 22 de dezembro de 2014 ( addinvrig.in ) e aqui está o arquivo de entrada fixo de hoje ( addinvrigFixed.in ). A linha crucial é: (x+(-x))+((-y)+y)=((-y)+y)+(x+(-x)).O poder das ferramentas de raciocínio automatizadas ainda é fascinante para mim, mesmo que elas não possam me impedir de interpretar mal os escritos de outras pessoas.

O uso de ferramentas de raciocínio automatizadas é surpreendentemente útil para mim, quando me deparo com teoremas citados onde não tenho certeza de como "interpretar" o texto :



x,yS(xy)=xy=xyxy=xy
aaSSaaSS

Eu adaptei meus arquivos de entrada do prover9 para esse teorema e imediatamente mostrei um contra-exemplo para o teorema, conforme citado. Modificar levemente as suposições produziu muitos teoremas verdadeiros semelhantes, o que torna mais provável que Karvellas realmente tenha declarado e provado um teorema correto, que só foi citado incorretamente aqui. Pesquisando a referência desse teorema, apenas apareceu outro artigo que citava Karvellas ainda menos preciso .


Esta é uma coleção inacreditavelmente incompleta de resultados auxiliados por computador para problemas específicos que são intratáveis ​​em geral se P! = NP. Talvez essa coleção deixe claro para pelo menos alguns leitores que todos nós tendemos a subestimar os poderes dos computadores nesse domínio. Muitas outras respostas a essa pergunta parecem sugerir que não haveria grandes consequências se os computadores obtivessem (um pouco) melhor na solução de problemas intratáveis. Mas os computadores ficam melhores em resolver problemas intratáveis ​​o tempo todo (porque gasta bastante tempo e dinheiro para fazer isso acontecer), e isso tem consequências muito reais. Se P = NP fosse provado, talvez a conscientização sobre o que os computadores realmente possam fazer (ainda hoje) aumentaria, e mais pessoas usariam computadores para ajudá-los nessas tarefas. (PS: Estou convencido de que P! = NP,

Thomas Klimpel
fonte
7

Há muitas opiniões sobre as implicações reais de P = NP. Como visto em outras boas respostas, existem principalmente duas escolas de pensamento. Uma é que um algoritmo de tempo P pode ser muito difícil ou inviável de implementar devido a "anomalias inesperadas" associadas à abstração. por exemplo:

  • o programa pode ser muito "grande" para codificar
  • pode haver uma constante muito grande envolvida de tal forma que, para todas as instâncias ao alcance da "computação terrestre", elas ainda são de longa duração, ou seja, a eficiência não "entra em ação", exceto em instâncias muito grandes. sabe-se que alguns algoritmos realmente se encaixam nesse caso, como apontado recentemente por Knuth (pergunta 15)

Em geral, estou procurando mais foco em algoritmos que funcionam rapidamente com relação a problemas cujo tamanho, n, é viável. A maior parte da literatura atual é dedicada a algoritmos assintoticamente grandes, mas são úteis apenas quando n excede o tamanho do universo.

Um famoso estudo de caso é realizado por Impagliazzo, como citado por J. em outra resposta. Entretanto, seu ensaio foi extrapolado um pouco nesse meio tempo. Aqui está uma excelente nova referência de um especialista que aborda essa questão em uma espécie de cenário futuro de ficção científica, ch2 / p11. resumindo

O bilhete de ouro: P, NP e a busca do impossível por Lance Fortnow

  • "se acontecer que P = NP e tivermos algoritmos eficientes para todos os problemas de NP, o mundo mudará de maneira a fazer a Internet parecer uma nota de rodapé na história. Não apenas seria impossível descrever todas essas mudanças, mas também o seria impossível prever as maiores implicações das novas tecnologias ".

  • Algoritmo implementado rapidamente no supercomputador. A Boeing imediatamente contrata para obter um melhor design de asa para uma nova aeronave, permitindo que voe de Londres para Sydney sem escalas.

  • Algoritmo de pesquisa usado para encontrar um novo algoritmo ainda mais rápido, otimizando a solução P = NP original. Termina com resultado de 42 milhões de linhas de código ininteligível. Chamado de "algoritmo Urbana"

  • Algoritmo usado para encontrar tratamentos de câncer personalizados / quase curas taylored para indivíduos. cura câncer, AIDS, diabetes, mas o resfriado comum permanece um mistério

  • O algoritmo de super escalonamento permite aos meteorologistas "fazer avanços incríveis na previsão do tempo, permitindo previsões precisas de temperatura, ventos, nebulosidade e precipitação quase um ano antes do tempo. Algoritmos similares agora salvam vidas ao prever com precisão tempestades, tornados e furacões, para que as pessoas possam prepare ou evacue conforme necessário. "

  • Reconhecimento de face altamente preciso

  • Computador pode reconstruir modelos 3D de uma cena em tempo real a partir de diferentes ângulos de câmera

  • Os algoritmos de computador controlam as operações da câmera para eventos esportivos (em vez de controlados por seres humanos)

  • Comentários e replays automatizados são gerados pelo algoritmo, incluindo ângulos e estatísticas bem escolhidos, e gerados em qualquer idioma em tempo real

  • Esportes / beisebol de fantasia assumem nova dimensão com simulações de alta precisão

  • Gosto da receita de alimentos aprimorado pelo algoritmo

  • O algoritmo pode ser usado para "aprender praticamente qualquer coisa, incluindo o que produz boa arte, música popular e palavras que mexem com a alma. Lembre-se de que P = NP significa que o que podemos testar, podemos encontrar. Então, quando você tiver um algoritmo processo para reconhecer a grandeza, você pode usar o algoritmo novamente para encontrar rapidamente essa grandeza. "

  • O político usa algoritmo de computador para reconhecer grandes discursos e gerar um que se encaixa nos padrões. A fala se torna viral na internet.

  • As pessoas geram obras de arte completas a partir de arte incompleta / inacabada, como sinfonias. eles usam algoritmo para gerar novos registros Beatles / Elvis. Nova arte, romances, peças de teatro e poesia, por exemplo, comédia romântica com Humphrey Bogart / Julia Roberts.

  • A Amazon pode criar um romance personalizado para indivíduos sob demanda. NBC cria séries de televisão de ação e aventura criadas inteiramente por computador

  • Realidade virtual simulada em videogames, permitindo ações dos jogadores, em vez de um conjunto fixo de possíveis enredos.

  • A aplicação da lei usa o algoritmo como "ferramenta incrível na solução de crimes, aparentemente fazendo o impossível na busca de suspeitos". O algoritmo de computador pode reconstruir faces prováveis ​​(para esboços compostos) usando apenas DNA. A polícia identifica um suspeito de assassinato usando uma pesquisa maciça no banco de dados de fotos da carteira de motorista alinhado com o esboço gerado (do DNA).

Infelizmente, pouco do que Fortnow descreve acima é suportado pela literatura científica atual, exceto talvez uma extrapolação imaginativa dos mundos de Impagliazzos. seria preciso muito mais para dissecar esse ponto a ponto, mas, para resumir, tudo parece divertido, mas fantástico / uma ilusão (ou talvez esse seja seu ponto velado). De fato, existem princípios científicos que estão em conflito com muitos dos itens. E note que Fortnow é um fã de esportes, então desenvolve uma metáfora extensa nessa área, mas isso poderia ser mais uma indicação de humanos pensando em ranhuras ?

Por exemplo, o "efeito borboleta" é conhecido por implicar que a previsão exata do tempo após um (digamos) horizonte de vários dias é impossível devido à "dependência sensível das condições iniciais" (e Fortnow mais tarde admitiu em seu blog críticas repetidas sobre exatamente isso ponto). Além disso, existem muitas evidências de que os computadores falham em tarefas altamente subjetivas ao ser humano, como gerar ou identificar arte influente (uma tarefa na qual mesmo os especialistas em seres humanos não conseguem consistentemente).

Na verdade, toda a questão está à beira de uma premissa contrafactual ou falsa . Observe que uma grande maioria de cientistas especialistas pesquisou pensar / acreditar, apesar da falta de provas incontestáveis ​​até agora, P ≠ NP. e é natural compará-lo com outras leis / restrições / limitações conhecidas como termodinâmica (por exemplo, impossibilidade de movimento perpétuo / energia livre ) e estatísticas, por exemplo, o "teorema do almoço sem almoço" .

Portanto, o ponto principal é que talvez até cientistas especialistas não possam prever exatamente o resultado de P = NP. Então, talvez a melhor resposta por enquanto seja admitir que os humanos não tenham uma boa resposta no momento.

vzn
fonte
11
nota: as duas escolas de pensamento são "P = NP pode não ser um grande negócio" para "seria um grande negócio", com Fortnow representando a última posição. mas, na verdade, essas duas escolas de pensamento estão fora do favor das principais hipóteses / conjecturas de CS. em outras palavras (como apontado por Aaronson ), não é o tipo de pergunta que pode ser abordada, por exemplo, meramente como Equipe A e Equipe B. a preponderância de evidências científicas parece indicar P ≠ NP ...
vzn
11
+1 para o livro Fortnow. Eu mesmo sugeriria. Uma lista mais curta de implicações (impressionantes) de P = NP está contida em cacm.acm.org/magazines/2009/9/… (também de Fortnow).
Fizz
7

P vs. NP, tecnicamente vs. moralmente

O(n2)O(nlgn)265536+21024n256 Russell Impagliazzo disse uma vez que ele consideraria a P versus NP problema como essencialmente resolvido se alguém mostra SAT pode ser resolvido emO(nlgn)

Então, o que acontece se P = NP é moralmente verdade?

QQverdade, todos esses problemas podem ser resolvidos muito rapidamente. Apenas para dar um exemplo, você pode aprender as melhores ponderações para modelos de aprendizado de máquina muito complicados. Você pode quebrar os protocolos de criptografia.

Se você sabe que deseja resolver um problema NP-complete não em entradas gerais, mas em entradas com propriedades específicas, não precisa se preocupar com o problema geral. Você só precisa resolver o problema mais simples. Infelizmente, muitas vezes não é fácil determinar com que tipo de dados você se importa na prática.

Kaveh
fonte
3

Que tipo de efeito quase imediato uma prova completa e precisa de P = NP, com uma solução fornecida, teria no mundo prático?

É provável que ocorram muitas coisas boas, mas ninguém se importaria.

O problema é que a base de (quase) toda a criptografia moderna se baseia na suposição de que P não é igual a NP. A criptografia que protege sua senha à medida que passa pela Internet e como é salva nos bancos de dados. A criptografia que protege os dados do cartão de crédito à medida que passa pela Internet ... A criptografia que protege os bilhões de transações financeiras diárias que vinculam nossa economia global ao organismo gigante que é.

Na melhor das hipóteses, P = NP significa que para. As pessoas voltam a usar dinheiro e os bancos tentam registrar esses saques em algum meio desconectado, já que as transações para um escritório central não são mais confiáveis. Isso dura talvez alguns meses até que uma melhor criptografia seja implementada globalmente. Melhor caso.

Na pior das hipóteses, P = NP significa que alguém quebra o mundo. A moeda é construída sobre o conceito de confiança. Você valoriza um dólar, porque confia que seu vizinho lhe dará um dólar em bens ou serviços por isso. Você valoriza o seu computador dizendo que possui 500 dólares no banco, porque pode passar o cartão e obter 500 dólares em bens e serviços ...

E se você não pudesse confiar nisso? Se P = NP, alguém poderia se passar por vários bancos, governo, pessoas - e efetivamente randomizar a quantidade de moeda em todas as contas. Exclua a moeda em todas as contas. Certamente, vários bancos têm backups para justificá-lo, mas há quanto tempo sua criptografia está quebrada? Quais transações foram boas e quais foram representadas? É impossível saber.

Uma vez que essa confiança é quebrada, o caos segue. Quaisquer benefícios de poder lidar com o Problema do Vendedor Viajante (por exemplo) são ignorados à medida que as pessoas lutam para se alimentar.

É provável que a realidade esteja em algum ponto intermediário, mas espero que isso mostre uma imagem suficientemente grande de quão importante é esse problema.

Telastyn
fonte
4
A criptografia não seria tão ruim quanto você sugere. Mesmo que P = NP, você não pode determinar deterministicamente os bits gerados aleatoriamente (por exemplo, chaves). É por isso que o teclado único sempre funcionará. As premissas de dureza computacional apenas ajudam a justificar o uso de chaves mais curtas e esquemas assimétricos.
Mdxn
2
@ MDX - já faz um tempo desde que eu estudei em profundidade, mas não importa se você pode prever as chaves, se você pode decodificar as chaves rápida e facilmente?
Telastyn
Para criptografia de chave privada, idealmente tentamos espalhar a aleatoriedade da sobre a mensagem de uma maneira que é difícil de desfazer. O benefício disso é que podemos usar chaves mais curtas, economizar tempo / espaço e ainda assim obter uma boa segurança. Se um invasor puder desfazer isso praticamente, isso não acontecerá. Se P = NP, teríamos de basear a segurança em problemas mais difíceis. A desvantagem é que a criptografia e descriptografia também são computacionalmente mais difíceis.
Mdxn
Embora um esquema de chave privada ainda possa reter a segurança teórica da informação da aleatoriedade da chave, um sistema de chave pública não o fará. Essa é a situação em que você seria capaz de extrair a chave. Novamente, no mundo em que P = NP, podemos usar um problema mais difícil para basear sua segurança, se tivermos um. Da mesma forma, seria menos eficiente.
Mdxn
11
@mdx: os blocos únicos não são uma solução viável para as necessidades de tráfego da Internet, porque o bloco precisa ser entregue com segurança ao destinatário antes de poder ser usado, e agora você acabou de dar um passo atrás no problema.
Mason Wheeler
2

Irá ocorrer uma queda maciça nas despesas com equipamentos, eletricidade e abordagens em nuvem. Muitas coisas estão sendo calculadas com força bruta agora, ou aproximações que ainda usam alguma força bruta pesada. Não faremos mais todos esses cálculos de força bruta paralelizados em massa.

Esse não é, de modo algum, o único uso da computação em nuvem, mas ainda será um fator perceptível no uso de energia, processamento na nuvem etc. Apenas a economia de energia pode ser notada em nossa pegada de carbono.

A IA também se tornará muito melhor. Finalmente, podemos ter um computador que pode ser o melhor jogador de GO, e sua calculadora gráfica irá derrotá-lo no xadrez.

dsollen
fonte
4
n×n19×19n×n
Você está assumindo que os problemas que atualmente resolvemos por força bruta caem em NP, e todos eles são instantaneamente tratáveis. Isso está longe de ser verdade.
Yves Daoust
0

E a conjectura que está sendo contestada não significa que todos os problemas de utilidade prática seriam resolvidos em um piscar de olhos. Em primeiro lugar, eles ainda podem ser mais difíceis do que NP.

Yves Daoust
fonte
-1 porque seu argumento não depende de nenhum detalhe do sistema sobre o qual ele deveria estar raciocinando. Pelo mesmo argumento, aprendemos a viver em um mundo sem carros, então eu não esperava que os carros causassem uma revolução. Por outro lado, aprendemos a viver em um mundo sem sapatos para tocar MP3, então eu não esperava que eles causassem uma revolução. Um desses exemplos é claramente falso, o outro provavelmente verdadeiro. Sua conclusão sobre P vs NP também pode ser.
David Richerby
@ DavidRicherby: obrigado por explicar o voto negativo.
Yves Daoust