O uso por Douglas Adams de 'Infinite Improbability' alude a P = NP?

7

Tendo acabado de despertar o antigo post P = NP , comecei a pensar: A descrição de Douglas Adams é da descoberta do drive Infinite Improbability através do uso do dispositivo Finite Improbability uma descrição de onde P = NP é usado para resolver um problema? Esta é sua explicação do problema?

Meu ponto, re-explicado: É meu entendimento que os 'cientistas' descobriram o impulso de improbabilidade finito, por algum algoritmo ou entendimento que os deixava colocar os parâmetros certos, acionando um cabo matemático. e saiam do drive de improbabilidade finita, eles sabiam que o trabalho de adivinhação. Eles então tentaram encontrar o drive infinito de improbabilidade da mesma maneira, aplicar um algoritmo e girar a alavanca.

Mas isso estava demorando demais (não era tempo polinomial, talvez fosse N ^ p, com p sendo a probabilidade), então os cientistas desistiram. No entanto, o descobridor do IID usou o drive Finite Improbability para adivinhar a solução para qualquer algoritmo ou equação, e os parâmetros envolvidos, ou seja, ele resolveu como um problema P como um problema NP.

Não consigo encontrar nada na web discutindo isso, mas posso ter perdido algo.

Isso é (ou algo similar) o que Douglas Adams quis dizer com essa descrição? Se não o que ele quis dizer?

    
por AncientSwordRage 26.09.2012 / 12:02
fonte

4 respostas

7

Mais ou menos.

Uma maneira de definir o NP é que a questão pode ser decidida em tempo polinomial, dado o acesso ao não-determinismo . Acontece que o não-determinismo pode ser considerado como equivalente a ter um computador que tenha sucesso se tiver uma probabilidade de sucesso diferente de zero. Essencialmente, o não-determinismo é equivalente ao dispositivo de probabilidade finita.

Assim, dado um dispositivo como um dispositivo finito de improbabilidade, qualquer evento improvável pode ser considerado provável. Podemos usar isso para construir um computador que tenha acesso ao não-determinismo. A distinção entre P e NP é então irrelevante, porque P e NP correm na mesma velocidade em um computador não determinístico. Teoricamente, P e NP ainda são distintos, mas a distinção não é mais útil.

    
por 26.09.2012 / 21:58
fonte
7

Vale a pena notar que o N em NP não pode ser aplicado apenas a problemas polinomiais: Se X for um conjunto específico de problemas que pode ser decidido em um tempo limitado por uma dada caracterização (isto é, polinômio para P ou exponencial para EXP ) por um determinístico Turing Machine (DTM), então NX será o conjunto de problemas que podem ser decididos por uma máquina de Turing (NTM) não determinística .

Então a questão é como o FID realmente funciona. Você tem que resolver um problema que pode ser decidido por um DTM em tempo polinomial toda vez que você quiser pular? Se você construísse uma máquina que usasse o FID para remover o não-determinismo exigido da execução de uma TM, você teria essencialmente construído um NTM. Isso realmente faz sentido, porque, embora o espaço do problema seja (ou melhor, pode ser) infinito, uma instância específica do problema é sempre finita. Portanto, a probabilidade de sempre "adivinhar" corretamente é finita. Nesse sentido, o FID seria o equivalente tecnológico ao modelo de computação de um NTM. Assim, em geral, em um universo com um FID, não há diferença prática entre qualquer X e sua correspondente NX de problemas, mas ainda seria desconhecido se eles são realmente iguais (como eles são definidos por TMs, não por IDs).

No entanto, não faz sentido argumentar sobre o tempo de execução total de um algoritmo que tritura uma entrada infinita, como em todos os casos, exceto alguns triviais, que seriam infinitos também.

Se IID é apenas algum tipo de problema matemático, que uma vez resolvido apenas lhe dá algumas dicas para construir uma máquina que implemente algum tipo de propulsão, então a questão é quão difícil é esse problema? Não temos nenhuma indicação de que cairia na classe dos problemas NP -complete. Há uma tonelada de PSPACE (= NPSPACE ) problemas e, na verdade, até mesmo alguns NEXPTIME . Se fosse PSPACE seu mágico tecnologicamente avançado, o FID não seria útil para você, você esperaria o mesmo tempo.

Assim, a relação entre qualquer X e NX seria como "unidade de improbabilidade fixa" e "unidade de improbabilidade finita". Parece que a unidade de improbabilidade infinita preferiria corresponder a uma máquina que decide cada problema no tempo constante , independentemente de sua complexidade em um DTM ou NTM porque um infinitamente improvável O evento é basicamente aquele que nunca acontece. Não há tais eventos pensáveis: até mesmo duas ogivas nucleares transformando-se espontaneamente em uma tigela de petúnias e um cachalote de aparência muito surpresa não é um evento impossível. É tão improvável que ninguém se importe em colocar um adesivo de advertência em tais ogivas.

Para finalmente responder sua pergunta; Não, eu não acho que Adams teria feito um erro tão de ciência pop. Suas partes sedutoras (na falta de um termo melhor) são sempre intencionais e funcionam mais de maneira irônica. O IID nos lembra um pouco da questão do não-determinismo, pois faz algo incrivelmente difícil de uma maneira espetacularmente eficiente, assim como um NTM faria. Mas essa semelhança é bastante superficial, como tentei salientar nos parágrafos anteriores.

    
por 27.09.2012 / 02:27
fonte
3

Eu acredito que você poderia usar uma unidade de improbabilidade infinita como parte de um solucionador de NP que faria P = NP.

Digamos que você ajuste seu IID para que, quando você selecionar aleatoriamente uma solução candidata, ela forneça a solução real. Por definição, para problemas de NP, verificar a exatidão da solução é relativamente fácil.

Feito.

A parte difícil é obter o impulso infinito de improbabilidade.

    
por 26.09.2012 / 18:22
fonte
2

Eu não vejo como isso poderia ser o caso. Muito brevemente, P e NP são duas classes de problemas computacionais. Os problemas P podem ser resolvidos em um período razoável de tempo com algoritmos bem conhecidos. Acredita-se que os problemas do NP (mas ainda não comprovados) sejam de tal ordem que a única maneira de resolvê-los é tentar todas as soluções possíveis, de forma aleatória, até que você obtenha a resposta correta. No entanto, todos os problemas de NP são similares de uma maneira que se você descobrisse um algoritmo que lhe permitisse resolver um NP mais rapidamente, esse algoritmo se aplicaria a todos os outros problemas NP. Se você já trabalhou com a matemática que mostra quantas soluções possíveis existem no espaço da solução, você pode ver por que isso foi um grande negócio. Números em alguns casos que são tão grandes que não têm nomes, apenas notações.

Existem implicações no mundo real se P acontecer igual a NP (e poucas que nós já não estamos vivendo se isso não acontecer). Por exemplo, um desses problemas é "Dada uma rota de entrega para esses 100 locais, que é o caminho mais eficiente a ser tomado". Se você pudesse resolver isso em uma quantidade razoável de tempo, sua empresa de entregas (provavelmente) consumiria 5% menos combustível por ano. Por sua vez, uma redução de 5% de algumas grandes frotas transportadoras, e nós provavelmente veríamos US $ 1,50 / galão de gasolina novamente nos Estados Unidos. E há muitos desses problemas. Computação gráfica, simulações de meteorologia, muitos deles. P = NP tem muitas implicações de ficção científica do mundo real (principalmente lidando com eficiências).

Mas a viagem instantânea para locais distantes não é uma delas.

    
por 26.09.2012 / 14:41
fonte