P, NP e máquinas de Turing especializadas

Sou um pouco novo, mas muito interessado no campo da teoria da computação e da complexidade, e quero esclarecer meu entendimento sobre como classificar problemas e quão fortemente os problemas estão relacionados à máquina que está sendo usada para resolvê-los.

Meu entendimento

• Máquina de Turing padrão - uma máquina de Turing que possui um alfabeto finito, número finito de estados e uma única fita infinita à direita
• Máquina equivalente a Turing - uma máquina de Turing que pode emular e ser emulada por uma máquina de Turing padrão (muitas vezes com alguma troca entre espaço e tempo alcançada pela emulação)
• P - a classe de problemas que podem ser resolvidos em tempo polinomial usando uma máquina de Turing padrão (definida acima)
• NP - a classe de problemas que podem ser verificados em tempo polinomial usando uma máquina de Turing padrão
• NP-complete- os problemas mais difíceis que ainda existem NP, nos quais todos os NPproblemas podem ser convertidos em tempo polinomial

Minha pergunta

São as classes de complexidade ( P, NP, NP-complete, etc) relacionados com o algoritmo, ou o algoritmo e a máquina?

Dito de outra maneira, se você pudesse criar uma Máquina Equivalente de Turing (que pode resolver todos os problemas que um Standard TM pode, mas em uma quantidade diferente de tempo / espaço) e essa nova máquina poderia resolver um NP-completeproblema no tempo que cresce como um polinômio em relação à entrada, isso implicaria P=NP?

Ou o NP-completeproblema deve ser solucionado em todas as máquinas de Turing possíveis em tempo polinomial para ser considerado P?

Ou entendo mal algo fundamental acima?

Eu dei uma olhada (talvez não com os termos de pesquisa corretos, eu não conheço muito bem o jargão), mas parece que a maioria das palestras / notas etc. se concentra em máquinas padrão, mas diz que máquinas personalizadas geralmente têm velocidade de tempo / espaço às custas do espaço / tempo, sem dizer como isso se aplica às classes de complexidade. Ainda não estou familiarizado o suficiente com o jargão nesse campo para encontrar trabalhos que expliquem isso.

Algoritmos e máquinas não estão definidos na sua pergunta e não acho que sejam necessários para perguntar o que você deseja perguntar.

As classes de complexidade são definidas usando máquinas de Turing. Essa é a definição deles. Se você quiser provar alguma coisa, precisará usar essas definições. Qualquer coisa sobre qualquer outro modelo não tem relação, a menos que você prove alguma correspondência entre esse modelo e as máquinas de Turing.

Deixe-me acrescentar que existe uma hipótese que diz que "computação" "eficiente" em qualquer "máquina" "razoável" capturará o mesmo número de funções teóricas. No entanto, não é uma declaração provável, a menos que se defina os termos citados. Podemos provar isso para muitas máquinas, mas nem todas. Ser equivalente a uma máquina de Turing não é suficiente, queremos que seja Fortemente , ou seja, devemos poder simular essas máquinas com máquinas de Turing e vice-versa de maneira eficiente. O legal de e$\mathsf{P}$$\mathsf{NP}$é que são classes muito robustas, ou seja, pequenas e grandes diferenças nos modelos de máquinas não mudam de classe. No entanto, é verdade o tempo todo. Por exemplo, eu posso definir um novo modelo simples de computação em que tenho uma operação básica que, em tempo constante, resolve um problema insolúvel em . Então é óbvio que este modelo não será fortemente equivalente às máquinas de Turing.$\mathsf{P}$

O exemplo acima foi artificial. No entanto, no momento, temos um modelo de computação que parece mais próximo da computação eficiente na prática do que as máquinas de Turing de tempo polinomial: máquinas probabilísticas de erro limitado / randomizadas de Turing, algoritmos eficientes nesse modelo são referidos como .$\mathsf{BPP}$

Muitos especialistas acreditam que mas estamos longe de provar isso.$\mathsf{BPP}=\mathsf{P}$

Temos outro modelo de computação que alguns especialistas esperam tornar viável no futuro: máquinas quânticas de Turing, algoritmos eficientes nesse modelo são referidos como . Não sabemos se é diferente de mas alguns especialistas conjeturam que é diferente e mais poderoso que .$\mathsf{BQP}$$\mathsf{P}$$\mathsf{P}$

Em resumo, se você quiser provar um resultado da teoria da complexidade sobre e , será necessário usar as definições originais usando as máquinas de Turing ou primeiro provar uma correspondência entre elas e as classes que você está usando com base em algum outro modelo de computação. Como mencionei acima, é bastante fácil criar modelos de máquinas em que o "tempo" polinomial neles possa resolver um problema (ou mesmo arbitrariamente mais difícil): basta adicionar uma operação básica ao seu modelo de máquina que resolva esse problema e deixe o "tempo" que a operação leva para ser uma unidade de tempo.$\mathsf{P}$$\mathsf{NP}$$\mathsf{NP}$

Apenas uma nota trivial para sublinhar que a simulação eficiente de uma máquina de Turing significa não apenas que ela pode simular o cálculo de uma máquina de Turing e vice-versa com eficiência (desaceleração do tempo polinomial); mas também que sua entrada / saída deve ser convertida eficientemente de um modelo para outro.

Um exemplo trivial: se você encontrar um dispositivo equivalente de Turing que pode resolver um problema SAT em tempo constante, mas usa como entrada uma pilha de bolas de gude (unárias), não poderá concluir nada. O mesmo se o seu dispositivo usar uma entrada binária, mas foram necessários um número exponencial de etapas para converter uma instância do SAT no formato de entrada usado por ele.

Sua compreensão é muito boa! Você também pode encontrar mais informações em um texto se estiver interessado, por exemplo, Introdução de Sipser à Teoria da Computação.

Existe uma idéia chamada tese de Church-Turing que diz que qualquer coisa que possa ser calculada de alguma forma, pode ser calculada usando uma máquina de Turing. (Não é comprovável, mas apenas uma ideia ou um tipo de lei da natureza que julgamos verdadeira).

Menciono isso porque há também a "Tese Estendida de Igreja de Turing", que diz que qualquer coisa que possa ser calculada no tempo polinomial de alguma forma, pode ser calculada no tempo polinomial usando uma Máquina de Turing.

Há boas razões para duvidar dessa conjectura porque conhecemos algoritmos de computação quântica que obtêm uma aceleração melhor que o polinomial sobre os algoritmos clássicos mais conhecidos. No entanto, além disso, acredita-se que qualquer máquina clássica que você possa construir (certamente qualquer variante de uma máquina de Turing) não possa ser exponencialmente mais rápida que uma máquina de Turing. Portanto, se sua "Máquina equivalente a Turing" pudesse executar um algoritmo que resolvesse um problema NP-Complete em tempo polinomial, então P = NP porque eu poderia convertê-lo em um algoritmo de tempo polinomial para o mesmo problema em uma TM.

Mas se você pensou em algum tipo de máquina equivalente a Turing, provavelmente uma das primeiras coisas que você faria seria descobrir como simulá-la com uma TM clássica e isso lhe diria se você tem uma conversão em tempo polinomial ou não. E a resposta quase certamente seria sim, exceto que talvez você possa ser exponencialmente mais lento (mas não mais rápido - pensamos, a menos que seja quântico, talvez).