Questão:
Qual foi o primeiro romance ambientado em universos onde P = NP?
Dr G
2011-01-12 03:43:30 UTC
view on stackexchange narkive permalink

Eu me pergunto se alguém escreveu um romance ambientado em um universo onde P = NP , caso haja mais de um, qual foi o primeiro?

enter image description here

Neste universo todos os problemas que pudessem ser verificados em tempo polinomial (NP) (dada a solução) também poderiam ser resolvidos em tempo polinomial (P).

por um bom motivo, imagino. Eu posso ver o diálogo agora.
Greg Egan escreveu inteiros escuros e luminosos, que tratam de calculabilidade e complexidade em um ambiente de álgebra puro. Se isso pode funcionar, um romance sobre P = NP também pode :)
Não é um romance, mas Russell Impagliazzo (um pesquisador da teoria da alta complexidade) escreveu um pequeno artigo descrevendo cinco mundos nos quais tais coisas acontecem (o universo Algorithmica tem P = NP, Cryptomania tem criptografia de chave pública garantida, etc.). Apenas pensei em mencionar, caso você esteja curioso para um ponto de vista mais teórico sobre como seria um mundo com P = NP. http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html
Dr. G +1, mas não tenho certeza de quais versões dos contos de Egan você leu: P, mas considerei que os valores de verdade das declarações aritméticas se comportavam como o spin de uma partícula quântica e o cálculo matemático os resultados estavam invertendo esses valores de verdade, em detrimento de um 'outro universo paralelo'. A própria física foi afetada pela mudança das regras da matemática, então houve um caos total quando os "outros" reagiram. (E sim, eu tenho um PhD em matemática pura)
... e como você sabe que P = NP não é verdadeiro nosso universo? Avise-me e compartilharei o $ 1 milhão com você.
@DavidRoberts Eu deveria ter formulado a questão como um romance ambientado em um universo onde sabemos P = NP :) Re: Egan, interpretei a história como uma reviravolta na definição intensional. Nossa teoria é baseada na definição intensional, não significa que o universo concorde, e como não tentamos verificar a versão extensional de nossas definições, o universo físico pode discordar.
Talvez todos eles ... Já que é um problema não resolvido neste momento. :-)
A [página inicial do MathFiction] (http://kasmana.people.cofc.edu/MATHFICT/) seria um bom ponto de partida para algo assim.
Você pode explicar, em termos * realmente * simples, o que P = NP significa e como saberíamos se um livro que estamos lendo estivesse naquele universo?
@Wikis: Em um universo P = NP _encontrar_ uma solução correta para uma grande e bem definida hierarquia de problemas seria tão complexa quanto _reconhecer_ que uma solução proposta para tal problema é correta. Por exemplo, em nosso universo, reconhecer que uma obra de arte é ótima parece muito mais fácil do que criar uma grande obra. Em um universo onde P = NP a quantidade de esforço necessária seria a mesma ou apenas modestamente maior quando considerada em termos do tamanho do problema a ser resolvido. A fácil quebra de quase todas as formas de criptografia é outro sinal de um universo P = NP.
@DrG: Greg Egan provavelmente poderia escrever um romance onde P e NP são os protagonistas. Esse cara faz Kim Stanley Robinson parecer George Lucas.
Dez respostas:
#1
+75
Kyle Jones
2012-01-05 06:12:59 UTC
view on stackexchange narkive permalink

Star Trek, Various, 1966 (ocorrência mais antiga)

P = NP no universo Star Trek, mas as pessoas de lá não estão cientes disso. Prova: Budap

  1. Existe criptografia, mas é sempre quebrável. P = NP permitirá que você decifre tudo, exceto blocos únicos, mas a Federação continua teimosamente a usar cifras baseadas em NP.

  2. A eficácia do tradutor universal. P = NP tornaria o aprendizado de novas linguagens muito fácil, pelo menos para um computador. Os sistemas de aprendizagem seriam tão simples e diretos de implementar que não sobraria um linguista com um emprego.

  3. A eficácia do bio-filtro. O transportador filtra rotineiramente organismos desconhecidos, vírus e outros perigos quando os tripulantes são transportados a bordo. Mas "bio-filtro" é um termo enganoso, pois traz à mente uma espécie de peneira que pega todas as coisas ruins e só passa as boas. Na realidade, executar esse "filtro" sobre os dados de transporte seria a mãe de todos os problemas de isomorfismo do subgráfico induzido, pois você teria que identificar todas as estruturas do tamanho de vírus em um organismo repleto de tais estruturas. P = NP elimina o expoente relacionado à entrada que torna esses problemas intratáveis ​​mesmo para pequenos gráficos.

  4. A inteligência da máquina autoconsciente é criada com facilidade. Wesley Crusher criou um por acidente. Richard Daystrom também. O computador Enterprise D preparou Moriarty em seus ciclos sobressalentes, Dr. Farallon criou o Exocomps e assim por diante. Tudo o que você precisa fazer é construir algo equivalente a um sistema de prova de teorema e deixá-lo funcionar por tempo suficiente para tropeçar na prova de que P ou alguma outra classe tratável é equivalente a NP e o sistema está pronto para as corridas.

Ou talvez os habitantes de Star Trek estejam colapsando a hierarquia polinomial por meios tecnológicos. A Federação, os Borg, etc. parecem ter acesso imediato a máquinas do tempo, buracos de minhoca, matéria exótica e sinalização superluminal, de modo que podem usar curvas fechadas semelhantes ao tempo para computação. Isso de acordo com Scott Aaronson permitiria que eles resolvessem problemas PSPACE completos de maneira eficiente.

1 por usar evidências do mundo para mostrar alguma coisa. Mais excelente.
Acho que eles simplesmente abordam os três pontos que você emite com o poder de computação bruto. Um DTM pode resolver precisamente os mesmos problemas que um NTM, mas leva mais tempo. Então, se suas habilidades de engenharia são loucas o suficiente, eles podem criar computadores muito rápidos (paralelos) (provavelmente também encontraram algumas heurísticas legais para alguns problemas NP-difíceis ao longo do caminho). Portanto, não tenho certeza de como seus argumentos se aplicam.
@Blue Talvez eu devesse ter escrito P = NP permite que você decifre tudo _útil_, exceto blocos de uso único. Se você não pode verificar a descriptografia em tempo polinomial, que é o que significa ter um criptosistema fora do NP, então _ mesmo com a chave_ a descriptografia não é computacionalmente viável. Isso para mim não é um criptosistema útil.
@bitmask: Está em algum lugar dos Manuais Técnicos que Star Trek executa o núcleo do computador dentro de um campo de dobra modificado onde o tempo corre em uma taxa diferente.
@MichaelEdenfield: Se * existem * técnicas de resolução de problemas estritamente mais poderosas do que um DTM muito rápido, e para aplicações práticas P e NP perderam relevância, isso por si só é uma evidência muito forte para P = NP no universo. Em um universo P! = NP, a descoberta de tais técnicas é muito improvável.
@Tynam P e NP são definidos estritamente em termos do que é possível fazer com máquinas Turnig determinísticas e não determinísticas; simplesmente não faz sentido falar sobre eles fora desse contexto. Já existem evidências de que os computadores quânticos * podem * fornecer uma maneira de realizar cálculos não determinísticos, por exemplo ...
@MichaelEdenfield: Bom ponto; Eu não tinha pensado sobre o ângulo do computador quântico / NDTM. Dito isso, a diferença prática entre um universo P = NP e um universo de computação ND significativamente mais poderoso parece provável ser pequena. (Mas então, não estou convencido de que o cérebro humano seja significativamente mais poderoso do que um DTM; paralelismo não é a mesma coisa que complexidade algorítmica.)
Você poderia colocar uma data para isso?
Data @AncientSwordRage para quê?
@Kyle a data em que você acha que a série de jornada nas estrelas foi retratada pela primeira vez como P = NP.
@AncientSwordRage Escolhendo meus exemplos, acho que teria que ser o primeiro episódio apresentando o uso do tradutor universal em uma situação de primeiro contato.Em TOS, seria o episódio 10 da primeira temporada, "The Corbomite Maneuver", quando a * Enterprise * encontrou Baalok e a bola divertida da Primeira Federação.
@kyle que o torna 1966, que é um contendor.Você se oporia a eu editá-lo em sua resposta?
@AncientSwordRage não, vá em frente.
#2
+54
Martha F.
2011-01-13 08:33:59 UTC
view on stackexchange narkive permalink

Antibodies, Charles Stross, 2000

Um conto que se baseia no fato de que resolver P = NP é um pré-requisito necessário para desenvolver uma inteligência de computador. Está disponível em seu livro Toast . Stross colocou o texto completo deste livro online. ( Este link o levará diretamente para a história.)

E de acordo com o site de Stross, a história foi:

Publicado na Interzone # 157; republicado em "The Year's Best Science Fiction # 18" (ed. Gardner Dozois). Mencionado na "Lista de leituras recomendadas" do Locus em 2000. Selecionado para o prêmio Theodore Sturgeon de 2001 (perdido para "Tendoleo's Story" de Ian MacDonald).

#3
+25
deworde
2011-09-26 04:42:50 UTC
view on stackexchange narkive permalink

O outro livro do Stross que lida com isso é The Atrocity Archives, onde Alan Turing resolveu P = NP, mas eles descobriram que isso permitia acesso aos Reinos Cthonic, então agora um ramo inteiro do Governo existe para evitar que esta descoberta se torne de conhecimento público.

#4
+18
Mike Scott
2011-01-13 13:20:03 UTC
view on stackexchange narkive permalink

Na série "Zones of Thought" de Vernor Vinges ("The Blabber", A Fire Upon the Deep , A Deepness in the Sky e o próximo The Filhos do Céu ), a computação é mais fácil em algumas partes da galáxia, permitindo coisas como inteligência artificial e viagens FTL.

Tem sido especulado (mas não há nenhuma evidência direta nos livros) que P = NP nessas zonas.

Existe alguma evidência indireta? Minha lembrança é que a computação é diferente fora da Zona Lenta (a tese de Church só se aplica à Zona Lenta) e algo como P = NP não precisa se aplicar ou mesmo fazer sentido lá.
Em * A Fire Upon the Deep *, os Skode Riders consideram a crença de Pham na criptografia de chave pública engraçada. Disto podemos concluir que `P == NP` no Além.
Não necessariamente - os computadores quânticos poderiam teoricamente lidar com problemas NP-completos em tempo polinomial, mesmo sem P = NP.
Não, eles não podem. As operações nas quais os algoritmos de criptografia de chave pública mais difundidos dependem de serem difíceis - fatoração, log discreto - não são (acredita-se que sejam) NP-completas. Esses são os problemas que os computadores quânticos são teoricamente capazes de quebrar em tempo polinomial. Dito isto, existem algoritmos de criptografia de chave pública que * são * baseados em problemas NP-completos, mas não estão em uso generalizado (ainda ...)
@BlueRaja Atualmente não sabemos como usar um computador quântico para resolver problemas NP completos com eficiência, mas você está afirmando que `P
@Code: Sim, desculpe, não falei com cuidado. Eu quis dizer que * não * é conhecido (ou acreditado) ser teoricamente possível.
Eu ia dizer Zonas do Pensamento. Não tenho certeza se é literalmente verdade que P = NP, em que é possível que _em qualquer local particular em uma zona_, nossa intuição de que você pode construir um problema NP que você não pode resolver facilmente seja verdadeira. Mas acho que é semelhante o suficiente para valer a pena mencionar, no sentido de que você pode mover (ou enviar uma mensagem) para uma zona superior, onde seu problema será facilmente resolvido.
#5
+5
M.K.
2011-05-26 03:51:45 UTC
view on stackexchange narkive permalink

Na fanfic Harry Potter e os métodos da racionalidade de Eliezer S. Yudkowsky, Harry obtém uma máquina do tempo e tenta fatorar o produto de dois grandes números primos usando esta máquina, com um resultado um tanto estranho. Portanto, não é totalmente dado que NP = P , mas parece provável.

Isso não faz sentido. Um problema pertence a P, se uma certa máquina de Turing resolvendo esse problema existir (a definição de NP é semelhante). Não importa se existem outros meios concebíveis de resolver esse problema. Ao hackear os loops de tempo, Harry foi além da questão P = NP.
Sim, se seu teste fosse bem-sucedido, isso significaria que há um dispositivo de computação "mais forte" do que a máquina de Turing e, portanto, ele refutou a tese de Church. Portanto, se você deixar NP definido usando máquinas de Turing, isso não provaria 'NP = P'.
IIRC, foi provado que P = PSPACE (que é mais forte do que P = NP) para uma máquina de Turing equipada com a capacidade de enviar dados para trás no tempo, mesmo que esteja sujeita à autoconsistência de Novikov.Ainda é possível que P = PSPACE para máquinas de Turing comuns, mas isso é considerado ainda menos plausível do que P = NP pelos teóricos da complexidade 'mainstream'.
#6
+2
Broklynite
2016-02-16 17:57:07 UTC
view on stackexchange narkive permalink

The Roaring Trumpet por Spague de Camp e Fletcher Pratt, publicado em maio de 1940 na revista Unknown. Aqui, os psicólogos postulam que os esquizofrênicos estão, na verdade, acessando mentalmente universos alternativos e, aplicando as equações adequadas, alguém poderia viajar até esse universo alternativo e trazer a mente da pessoa de volta ao nosso universo. Foi um exercício intelectual que o protagonista Harold Shea decide testar. Ele jocosamente se refere a viagens via silogismóvel, mas envolve estudar e construir a lógica do destino do universo e recitá-la em voz alta. Geralmente começa com "se P é igual a não P ..." E continua a partir daí. Toda a série Enchanter os faz passar pela mitologia, contos de fadas e obras clássicas ao fazer isso.

Eu suspeito, nunca tendo pensado muito nisso, que ao prefaciar com P = NP, eles estavam distinguindo os universo como um no qual a mágica funciona.

#7
+1
Gelvis
2011-01-13 22:16:51 UTC
view on stackexchange narkive permalink

Nemesis, Isaac Asimov, 1989

Fala sobre as imposibilidades e as implicações de um universo onde as leis da física não se aplicam

Forneça uma data com sua resposta da próxima vez e explique por que isso se relaciona * explicitamente * a P = NP.
#8
+1
aquaherd
2011-09-21 05:37:04 UTC
view on stackexchange narkive permalink

O efeito da prática , David Brin, 1984

Este parece um candidato provável. No universo representado, uma sonda robótica do nosso universo começa a se auto-otimizar tanto física quanto mentalmente, enquanto a inteligência humana permanece inalterada. Os objetos físicos também tendem a se auto-otimizar: um trenó de madeira desenvolve lubrificante para deslizar facilmente na estrada. Este efeito de prática pode ser potencializado por um estado especial de transe onde a solução aparece imediatamente por si mesma, portanto, objetos inanimados realizam uma evolução de amplo alcance dentro do tempo não polinomial (Buscando um conjunto quase infinito de soluções possíveis dentro de um curto período de tempo) . Este universo realmente transcende P = NP.

Por favor, [editar] por que você acha que este é o caso.
#9
  0
jersey
2018-08-02 08:53:13 UTC
view on stackexchange narkive permalink

Na história Starshield Sentinels de Margaret Weis e Tracy Hickman, havia computadores / inteligências artificiais que podiam responder a qualquer pergunta instantaneamente , enviando a pergunta de volta no tempo para si mesma , dando "tempo" para resolvê-lo. O único problema era que o computador precisava ficar "acordado" por tempo suficiente para resolvê-lo (algo como Deep Thought do Guia do Mochileiro das Galáxias, precisando de 10 milhões de anos para resolver a questão da vida, do universo e de tudo).

Embora eu não saiba se isso se aplica exatamente a tudo P = NP, ele resolve a cláusula variável / resolve na questão.

É claro que todos os computadores enlouquecem e tentam matar todos na história. Não podemos parar de tentar inventar robôs assassinos agora?

#10
-2
Michael Kohne
2011-09-27 06:38:38 UTC
view on stackexchange narkive permalink

Se não me engano, em ' The Ragged Astronauts' de Bob Shaw, um dos personagens passa um tempo explicando como pi é 3 para outro. Se pi for 3, só posso imaginar como é o resto da física. (Eu só me lembro da cena porque toda a cena estava um pouco fora do lugar, o que era bastante incomum para o livro - caso contrário, era um conto legal).

Como isso se relaciona com p = np?


Estas perguntas e respostas foram traduzidas automaticamente do idioma inglês.O conteúdo original está disponível em stackexchange, que agradecemos pela licença cc by-sa 2.0 sob a qual é distribuído.
Loading...