Algoritmos de DNA e NP-completude

21

Qual é a relação entre algoritmos de DNA e as classes de complexidade definidas usando máquinas de Turing? O que as medidas de complexidade como tempo e espaço correspondem nos algoritmos de DNA? Eles podem ser usados ​​para resolver instâncias de problemas NP-completos, como o TSP, que as máquinas von Neumann não conseguem resolver na prática?

Aadita Mehra
fonte
2
Eu postei uma pergunta de acompanhamento aqui: cstheory.stackexchange.com/questions/2758/…
Aaron Sterling

Respostas:

31

Resposta do Soundbite: A computação em DNA não fornece uma varinha mágica para resolver problemas completos de NP, mesmo que alguns pesquisadores respeitados na década de 1990 pensassem por algum tempo.

O experimento inaugural de computação em DNA foi realizado em um laboratório liderado pelo renomado teórico dos números Len Adleman. Adleman resolveu um pequeno problema do vendedor ambulante - um conhecido problema de NP-completo, e ele e outros pensaram por um tempo que o método poderia aumentar. Adleman descreve sua abordagem neste pequeno vídeo , que eu acho fascinante. O problema que encontraram foi que, para resolver um problema de TSP de tamanho modesto, eles precisariam de mais DNA do que o tamanho da Terra. Eles haviam descoberto uma maneira de economizar tempo aumentando a quantidade de trabalho realizado em paralelo, mas isso não significava que o problema do TSP exigisse menos recursos exponenciais para resolver. Eles apenas mudaram o custo exponencial de quantidade de tempo para quantidade de material físico.

(Há uma pergunta adicional: se você precisar de uma quantidade exponencial de máquinas para resolver um problema, exige automaticamente uma quantidade exponencial de tempo, ou pelo menos pré-processamento, para construir as máquinas em primeiro lugar? Vou deixar esse problema para um lado, no entanto.)

Esse problema geral - reduzindo o tempo que uma computação exige às custas de algum outro recurso - apareceu muitas vezes em modelos de computação inspirados biologicamente. A página da Wikipedia sobre computação em membrana (uma abstração de uma célula biológica) diz que um certo tipo de sistema de membrana é capaz de resolver problemas completos de NP em tempo polinomial. Isso funciona porque esse sistema permite a criação de subobjetos exponencialmente muitos dentro de uma membrana geral, em tempo polinomial. Bem ... como é que uma quantidade exponencial de matéria-prima chega do mundo exterior e entra através de uma membrana com área de superfície constante? Resposta: não é considerado. Eles não estão pagando por um recurso que a computação exigiria.

Finalmente, para responder a Anthony Labarre, que vinculou a um artigo mostrando AHNEPs pode resolver problemas de NP-completos em tempo polinomial. Há até um artigo mostrando que os AHNEPs podem resolver 3SAT em linearTempo. AHNEP = Rede híbrida de aceitação de processadores evolutivos. Um processador evolutivo é um modelo inspirado no DNA, cujo núcleo possui uma cadeia que em cada etapa pode ser alterada por substituição, exclusão ou (importante) inserção. Além disso, um número arbitrariamente grande de strings está disponível em todos os nós e em cada etapa da comunicação, todos os nós enviam todas as strings corretas para todos os nós conectados. Portanto, sem custo de tempo, é possível transferir quantidades exponenciais de informações e, devido à regra de inserção, as seqüências individuais podem se tornar cada vez maiores ao longo do cálculo, por isso é um golpe duplo.

Se você está interessado em trabalhos recentes em biocomputação, realizados por pesquisadores que se concentram em cálculos práticos do mundo real, posso oferecer esta resenha que escrevi recentemente para o SIGACT News, que aborda brevemente várias áreas.

Aaron Sterling
fonte
@ Aaron: Obrigado! Agora eu tenho que ir e ler sua resenha.
Aadita Mehra
Eu não poderia ter dito melhor. Isso também é válido para uma série de outras técnicas de solução de problemas de inspiração biológica, como algoritmos genéticos e dobragem de proteínas.
usar o seguinte comando
6
r>2Gmc2
5
(continuação) Portanto, sua quantidade exponencial de máquinas tem um raio exponencial. Como você não pode sinalizar mais rápido que a luz, um sinal de um lado para outro leva um tempo exponencialmente longo para chegar ao outro lado; portanto, se todas as máquinas contribuírem para a resposta, é impossível resolver o problema em menos do que exponencial Tempo.
quer
@ Joe: Obrigado. :-) Seria bom eu citar parte de seus comentários em uma pergunta de acompanhamento? Estou interessado em formalismos que capturam afirmações como "O poder computacional escala no máximo linearmente na massa". Quanto Kolmogorov complexidade está lá por polegada quadrada, etc.
Aaron Sterling
13

Isso depende muito do seu modelo.

Na realidade, a computação em DNA segue leis físicas (não-relativísticas) e, portanto, pode ser simulada em um computador quântico. Portanto, o melhor que você pode esperar é que ele possa resolver problemas completos do BQP. No entanto, é muito improvável que isso seja verdade (o DNA é bastante grande e, portanto, a coerência não é realmente um problema), e por simulação é quase certamente P. É importante notar, no entanto, que isso é eficiência em termos do número de átomos usados ​​e, francamente, os átomos são suficientemente baratos para que esse número seja astronômico, fazendo uma simulação prática de um tubo de ensaio cheio de DNA bem fora do domínio do que é atualmente possível.

Como resultado, muitas pessoas optam por trabalhar com modelos que se aproximam do que acontece muito bem na prática, mas quebram quando são levados ao extremo. Um exemplo disso é o modelo abstrato de ladrilhos, que é completo para NEXP (veja o artigo de Gottesman e Irani da FOCS no ano passado).

Joe Fitzsimons
fonte
Obrigado pela idéia inteligente, de ver a computação em DNA como um sistema físico! Vou olhar para o artigo que você vinculou. Obrigado novamente.
Aadita Mehra 4/11
@Aadita: Não há problema. Espero que seja útil.
Joe Fitzsimons
11
O modelo de ladrilhos Wang não se destina a modelar a dinâmica física. Quando interpretada como uma ferramenta para predizer o estado futuro de um sistema físico, o que uma telha válida de Wang faz é prever o estado mais provável de um sistema em equilíbrio termodinâmico; ou seja, menor energia. Mas a termodinâmica não dá idéia de quanto tempo um sistema pode levar para convergir para o equilíbrio; para isso você precisa de cinética. Muitos sistemas têm um equilíbrio termodinâmico que é alcançado somente após o tempo exponencial. Para "complexidade computacional física", use cinética, não termodinâmica; por exemplo, o modelo de montagem de ladrilhos.
Dave Doty
@ Dave: Obrigado pela informação. Devo admitir que sou bastante ignorante da área e talvez tenha escrito muito mal essa parte da resposta. Não pretendia afirmar que se acreditava ser um modelo da dinâmica.
Joe Fitzsimons
2

Esta é uma resposta parcial

No artigo da Wikipedia que você mencionou, os algoritmos de computação molecular de DNA que resolvem problemas completos de NP não provam que os problemas completos de NP são solucionáveis ​​em tempo polinomial em máquinas seqüenciais (supondo que na prática, na prática, significa tempo polinomial). A computação em DNA pode ser considerada uma forma paralela de computação. Finalmente, do ponto de vista da teoria da computabilidade, a computação em DNA não é mais poderosa que as máquinas de Turing.

Mohammad Al-Turkistany
fonte
1

Este artigo pode ser interessante para você - aliás, ficaria grato se alguém pudesse esclarecer a declaração chocante que constitui seu título.

Anthony Labarre
fonte
2
Alguns problemas fora do PTIME podem ser resolvidos por máquinas paralelas em tempo polinomial. Isso não é paradoxal, pois o PTIME fala sobre os problemas solucionáveis ​​por uma classe específica de máquinas seqüenciais em tempo polinomial.
Charles Stewart
5
Tentei esclarecer a resposta que publiquei.
Aaron Sterling