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.