P contém idiomas incompreensíveis? (Wiki da comunidade TCS)

Resposta: desconhecido

Muito obrigado a todos que ajudaram a refinar esta questão e as definições a ela associadas.

As definições deste wiki forneceram o ponto de partida para o wiki mais recente do TCS " P contém idiomas cuja existência é independente do PA ou ZFC? (Wiki da comunidade TCS) ".

O wiki mais recente é preferido porque suas definições e nomenclaturas são substancialmente mais sofisticadas do que as deste wiki mais antigo.

Em particular, a nomenclatura deste wiki mais antigo, incompreensível, linguagens compreensíveis e TMs são suplantadas no wiki mais recente pelo críptico gnóstico . Além dos detalhes de definição - que, no entanto, são importantes - as duas wikis abordam uma classe de perguntas semelhante. $\Leftrightarrow$ $\Leftrightarrow$

Respostas adicionais são bem-vindas

Respostas adicionais são bem-vindas (escusado será dizer), e é provável que um ajuste de definição adicional seja apropriado. Uma lição principal foi que essa classe de perguntas é difícil de formular e ainda mais difícil de responder rigorosamente.

Como pano de fundo, a resposta de Sasho Nikolov foi classificada como "aceita", porque forneceu uma formulação que capturou a intenção da pergunta: a resposta para a pergunta é (aparentemente) desconhecida.

A valiosa resposta de Philip White motivou a definição gradual de MTs incompreensíveis, versus fortemente incompreensíveis, versus canonicamente incompreensíveis (de acordo com a lista "definições classificadas de incompreensibilidade" abaixo).

A declaração a seguir da pergunta incorpora provisoriamente idéias e sugestões valiosas fornecidas por Tsuyoshi Ito, Marzio De Biasi, Huck Bennett, Ricky Demer, Peter Shor e também um valioso post de Luca Trevisan .

Definição formal

Máquinas de Turing incompreensíveis são definidas (no ZFC) da seguinte maneira:

D1 Dada uma máquina de Turing M que provadamente pára para todas as seqüências de entrada, M é chamado de incompreensível se a seguinte declaração não for comprovável nem refutável por pelo menos um número real semidefinido positivo : $r$

Instrução: O tempo de execução de M é com relação ao comprimento de entrada ${O}(n^r)$ $n$

Por outro lado, M é chamado compreensível se não for incompreensível.

disambiguating decidable

A entrada da Wikipedia " Problema indecidível: exemplos de afirmações indecidíveis " analisa de forma concisa os diferentes sentidos do termo "indecidível" que são habituais na literatura teórica da prova versus teórica da computabilidade. Com o objetivo de evitar ambiguidade, as definições e perguntas feitas empregam exclusivamente a terminologia "nem provável nem refutável".

Outras referências a esse respeito são as notas do curso de Jeremy Avigad " Incompletude via Halting Problem ", o ensaio de Scott Aaronson no blog " Teorema de Rosser via máquinas de Turing " e o post de Luca Trevisan no blog Duas perguntas interessantes .

Sobre a existência de máquinas de Turing incompreensíveis

A existência de máquinas de Turing incompreensíveis segue-se concretamente de uma construção de Emmanuele Viola e amplamente do arcabouço teórico da complexidade de Juris Hartmanis. Em particular, a construção de Viola fornece, através dos métodos das notas do curso de Jeremy Avigad (como eu as entendo), o seguinte lema:

Lema [Implicação da Viola]
(se um idioma L for aceito por uma MT compreensível) (L é aceito por uma MT incompreensível). $\to$

Respeitar a naturalidade na definição de incompreensibilidade

É natural se perguntar se a implicação inversa à implicação de Viola é verdadeira.

As considerações de naturalidade exigem que a implicação inversa seja colocada com cuidado, pois o comentário de Philip White abaixo mostra como reduzir trivialmente TMs incompreensíveis a TMs compreensíveis via polilimitros , que são módulos computacionais que (com efeito) "acolhem" o tempo de execução de uma máquina incompreensível para reduzi-lo a uma máquina compreensível.

Em particular, é natural exigir que não “ mascaremos esteticamente elementos antigos de incompreensibilidade, introduzindo novos elementos de incompreensibilidade ”. O principal desafio associado à pergunta é o seguinte: "Existe uma definição natural de incompreensibilidade?" ... que (dada a discussão aqui do TCS) talvez devêssemos considerar uma meta-pergunta não trivial que pode ter mais de uma resposta natural.

Tendo em vista esse princípio norteador da naturalidade, são definidas as seguintes definições de incompreensibilidade.

Definições graduadas de incompreensibilidade

D2 Dizemos que uma máquina de Turing M é eficiente se tiver um expoente de tempo de execução tal que a linguagem L que M aceita não seja aceita por nenhuma outra TM que tenha um expoente de tempo de execução menor que . $r$ $r$

D3 Dizemos que uma linguagem L é incompreensível se for aceita por (a) pelo menos uma máquina de Turing M que é eficiente e incompreensível e, além disso (b) não existe TM eficiente e compreensível que, provavelmente (em ZFC) aceite EU.

D4 Dizemos que uma MT incompreensível é fortemente incompreensível se o idioma que aceita é incompreensível.

D5 Dizemos que uma MT fortemente incompreensível é canonicamente incompreensível se for eficiente.

Essas definições garantem que toda linguagem incompreensível seja aceita por pelo menos uma TM canonicamente incompreensível e, além disso - em vista de D3 (a) e D3 (b) - não existe redução trivial de polilimitro de uma TM canonicamente incompreensível para uma TM compreensível que provavelmente reconhece o mesmo idioma.

As três perguntas feitas

Q1 A classe de complexidade P contém idiomas incompreensíveis?

Q2 Pelo menos uma linguagem incompreensível pode ser representada concretamente? (se sim, forneça um exemplo construtivo).

Q3 Pelo menos uma MT canonicamente incompreensível pode ser representada concretamente? (se sim, forneça um exemplo construtivo).

Motivação

As propriedades incompreensíveis da classe de complexidade P impedem o entendimento de uma ampla classe de problemas que (para o proponente original dessa pergunta ) inclui o quebra-cabeça dos olhos azuis de Terry Tao , Dick Lipton e o jogo de escolha de urna de Ken Regan , e sua hibridação em o contexto do Paradox da Newcomb através do jogo Newcomb do Balanced Advantage .

Como a monografia de Juris Hartmanis, cálculos factíveis e propriedades de complexidade comprovável (1978) coloca:

Os resultados sobre a complexidade dos algoritmos mudam radicalmente se considerarmos apenas as propriedades dos cálculos que podem ser provadas formalmente.

A luta para construir definições bem postuladas e postulados que capturam o insight de Hartmanis nos ajuda a compreender melhor que a classe de complexidade P possui algumas linguagens extremamente peculiares, que são reconhecidas por máquinas de Turing extremamente peculiares, cujas propriedades somos (atualmente ) muito longe de entender. É surpreendente que, em um sentido completamente rigoroso, não se saiba atualmente se a classe de complexidade P é compreensível.

Muito obrigado a todos que contribuíram com comentários e respostas.

cc.complexity-theory complexity-classes turing-machines decidability John Sidles
fonte

Por favor, defina o termo "(uma máquina de Turing) estando decididamente em P."

Tsuyoshi Ito

No problema declarado na definição de “incompreensível em P”, qual é exatamente a entrada? A máquina de Turing faz parte da entrada ou é fixa? Além disso, como um número real é especificado como uma string?

Tsuyoshi Ito

r

$r$

M

$M$

Como Sasho explicou preventivamente, o problema declarado na definição de “incompreensível” na revisão 4 é decidível para cada M. Tenho medo de que você esteja cometendo um erro elementar aqui. Se você ainda tiver problemas para entendê-lo, esta postagem de Rafael e o link podem ser úteis. Votei em encerrar isso como uma questão não real.

Tsuyoshi Ito

C n^{k}

$Cn^k$

C

$C$

k

$k$

Respostas:

(Estou me aposentando por não ter mais relevância na parte da resposta que acabou de explicar por que não há instâncias indecidíveis de um problema / nenhum algoritmo polytime com limite de tempo indiscutível)

$T$ $M$ $M$ $T$

$M$ $M$
$M$ $M'$

Portanto, parece que a resposta para sua pergunta é "não": qualquer idioma decidível no polytime por alguma máquina é decidido por uma máquina comprovadamente polytime. Mas talvez sua pergunta deva ser:

$M$ $M'$ $M$

Eu suspeito que a resposta seja sim, mas agora não tenho mais tempo para me dedicar a isso.

Sasho Nikolov
fonte

------ Existem dois sentidos distintos da palavra indecidível em matemática e ciência da computação. O primeiro deles é o sentido teórico da prova usado em relação aos teoremas de Gödel, o de uma afirmação não ser comprovável nem refutável em um sistema dedutivo especificado. ... Por causa dos dois significados da palavra indecidível, o termo independente às vezes é usado em vez de indecidível para o sentido "nem provável nem refutável".

John Sidles

Obrigado, Sasho! Também cheguei a essa apreciação, mas o postulado pode ser alterado pela distinção da Wikipedia: "Existem dois sentidos distintos da palavra indecidível na matemática e na ciência da computação. O primeiro deles é o sentido teórico da prova usado em relação aos teoremas de Gödel, o de uma afirmação não ser comprovável nem refutável em um sistema dedutivo especificado ... Por causa dos dois significados da palavra indecidível, o termo independente às vezes é usado em vez de indecidível para o sentido 'nem provável nem refutável' ". Assim, espero esclarecer a questão hoje mais tarde.

John Sidles

Solicitado em grande parte por seus comentários ponderados, o atributo ambíguo "decidível" agora foi substituído pelo atributo (esperançosamente inequívoco) "nem provável nem refutável". Pela qual sua ajuda é apreciada e agradecemos.

John Sidles

por favor, verifique minha resposta atualizada

Sasho Nikolov

Obrigado Sasho. Eu também tenho que fazer uma pausa até amanhã, no entanto, na primeira leitura, sua sugestão final parece muito proveitosa, e espero responder a ela em breve. Obrigado novamente.

John Sidles

Apenas um comentário estendido tentando interpretar a pergunta.

$M$ ~~promete-se parar~~ $M$ ~~número real semidefinido positivo~~ $r$ ~~questão~~ $Q_{M,r}$

OPÇÃO 1

$Q_{M,r}(n)$ $M$ $n^r$ $n$

$2^n$ $M$ $\Rightarrow$

OPÇÃO 2

$Q_{M,r}$ $M$ $O(n^r)$

$\Rightarrow$

E se você perguntar: "Ok, mas podemos calcular o valor 1 ou 0 para criar o algoritmo que responde à pergunta da opção 2?", Então voltamos a isso:

$Q_{r}(M)$ $M$ $O(n^r)$ $M$

Marzio De Biasi
fonte

Marzo, obrigado por esta resposta e por seu comentário acima. O termo ambíguo "decidível" já foi abandonado - significava coisas diferentes para comunidades diferentes - a favor do idioma da prova teórica "nem provável nem refutável". Para a fila de esclarecimentos de alterações para a versão editada de amanhã da pergunta (que, esperançosamente, será a rigorosa final da pergunta), a frase "Para todos os n " será anexada, conforme sua Opção 1. E, finalmente, a gratidão e o agradecimento são estendidos a você e a todos, pela ajuda em fazer a pergunta de forma rigorosa e clara.

John Sidles

M

$M$

M

$M$

O (n^{r})

$O(n^r)$

M

$M$

O (n^{r})

$O(n^r)$

Marzo, ok e obrigado. Além disso, para estabelecer a "Implicação da Viola", precisamos anexar o argumento da Seção 3 das notas do curso de Jeremy Avigad (conforme vinculado na pergunta) à construção da Viola ... a pergunta alterada esclarecerá esse ponto. Escusado será dizer que o processo de esclarecer as definições foi 10X ++ mais árduo do que eu previa originalmente ... o que talvez seja o ponto principal da questão. Obrigado novamente.

John Sidles

A resposta para sua pergunta nº 1 é definitivamente "não". Como acredito que alguém apontou na seção (muito longa) de comentários, você pode facilmente adicionar um "limite de polil" a uma máquina. Ou seja, mesmo que você não saiba o que é r, se adivinhar um número inteiro maior que r (isso é definitivamente possível, obviamente), você pode configurar uma máquina aérea que simula sua máquina de Turing "incompreensível" e forçá-la parar de rodar em tempo polinomial ... sem alterar o idioma que a máquina de Turing aceita. Dessa maneira, você pode converter qualquer máquina de Turing polinomial "incompreensível" em uma máquina de Turing polinomial "compreensível", o que significa que não há linguagem em P que possa ser decidida por máquinas de Turing exclusivamente "incompreensíveis".

Eu espero que isso ajude. A menos que eu tenha interpretado completamente mal sua pergunta e sua intenção, minha resposta certamente está correta; não é de todo uma questão em aberto.

Philip White
fonte

A propósito, se você deseja um bom exemplo de candidato para o que chama de algoritmo "incompreensível", consulte scholarpedia.org/article/Universal_search . O algoritmo de busca universal para resolver o SAT segue a sua definição de incompreensível se P = NP for formalmente independente.

Philip White

você sabe alguma coisa sobre a pergunta final da minha resposta? Eu acredito que essa é a única pergunta que ainda não é obviamente trivial ... para mim é

Sasho Nikolov

@ Phillip White, a definição é cuidadosamente construída para evitar a construção que você fornece. Como supondo que o tempo de execução de M seja indecidível para algum expoente r , adivinhemos um valor r ' > r e instalemos um r' -polylimiter em uma máquina modificada M 'que reconheça o mesmo idioma que M e, em seguida, para M' a instrução "o tempo de execução de M 'é O (n ^ r) em relação ao comprimento de entrada n" ainda é indecidível. Concordo, porém, que precisamos pensar com cuidado se TODOS os jogos de gato e rato com polilimitadores especificados por oráculo são excluídos (como é a intenção) --- e, portanto, votei sua resposta!

John Sidles

Ah, e desde que o comentário de Sasho se sobrepôs ao meu, deixe-me expressar minha apreciação pela pergunta final na resposta de Sasho , que (de acordo com minha atual compreensão) obstrui artisticamente a introdução de polilimitadores derivados de oráculos. Como antes, terei que pensar sobre isso por um dia ou dois. Obrigado novamente, Philip.

John Sidles

Desculpe, eu deveria ter lido a resposta de Sasho Nikolov com mais cuidado; Acabei de ver a palavra "sim", opa. Examinarei a última pergunta em um momento e verei se tenho algo útil a dizer.

Philip White