P contém idiomas cuja existência é independente do PA ou ZFC? (Wiki da comunidade TCS)

14

Resposta: desconhecida.

As perguntas são naturais, abertas e aparentemente difíceis; a questão agora é um wiki da comunidade.

Visão geral

A questão procura dividir as linguagens pertencentes à classe de complexidade  - junto com as máquinas de decisão de Turing (TMs) que aceitam essas linguagens - em duas subclasses complementares:P

  • linguagens gnósticas e MTs (que são viáveis ​​para validar / entender), versus
  • linguagens enigmáticas e TMs (inviáveis ​​para validar / entender).

Definições: números gnósticos vs criptográficos , TMs e idiomas

Dentro das estruturas de axioma PA e ZFC , distinguimos máquinas e idiomas de Turing gnósticos de criptografados da seguinte maneira:

D0   Dizemos que um número real computável  é gnóstico se estiver associado a um conjunto não vazio de TMs, com cada TM especificada no PA como uma lista explícita de números que compreendem código válido em uma TM universal, de modo que, para qualquer precisão fornecido como entrada, cada TM provável (em ZFC) pára com um número de saída que provável (em ZFC) satisfaz .ϵ > 0 o r - ϵ < o < r + ϵrϵ>0 0or-ϵ<o<r+ϵ

Observação   Sabe-se que alguns reais computáveis ​​não são gnósticos (para um exemplo concreto, veja a resposta de Raphael Reitzig à pergunta de jkff " Existem provas de existência de algoritmos não construtivos? "). Para evitar lidar com esses números computáveis, porém inábeis, é imposta a restrição de que os expoentes em tempo de execução sejam computáveis ​​por TMs explicitamente enumeradas no PA (em contraste com as TMs implicitamente especificadas no ZFC). Para uma discussão mais aprofundada, consulte a seção Considerações de definição (abaixo).

Agora, buscamos definições que capturam a intuição de que a classe de complexidade inclui um subconjunto de linguagens criptográficas às quais nenhum expoente de tempo de execução (gnóstico) pode ser atribuído. P

Para olhar adiante, a definição final ( D5 ) especifica a idéia de uma decisão canonicamente enigmática , cuja definição é criada com o objetivo de evitar reduções que mascaram (trivialmente) os cálculos enigmáticos, sobrepondo epicálculos computacionalmente supérfluos. A lógica e as fontes dessa definição-chave são discutidas mais adiante - sob o título Considerações Definicionais  - e as contribuições dos comentários de Timothy Chow, Peter Shor, Sasho Nikolov e Luca Trevisan são reconhecidas com gratidão.

D1   Dada uma máquina de Turing M que para todas as seqüências de entrada, M é chamado de enigmático se a seguinte declaração não for comprovável nem refutável por pelo menos um número real gnóstico  :r0 0

Instrução: O tempo de execução de M é com relação ao comprimento de entradanO(nr)n

Máquinas de Turing que não são enigmáticas, dizemos, são TMs gnósticas.

D2   Dizemos que uma máquina de Turing de decisão M é eficiente se tiver um expoente de tempo de execução gnóstico  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 gnóstico menor que  .rrr

D3   Dizemos que uma linguagem L é enigmática se é aceita por (a)  pelo menos uma máquina de Turing M é eficiente e enigmática e além disso (b)  nenhuma MT que seja eficiente e gnóstica aceita L.

Para expressar D3 de outra maneira, uma linguagem é enigmática se as TMs que aceitam essa linguagem com mais eficiência são enigmáticas.

Idiomas que não são enigmáticos, dizemos que são idiomas gnósticos .

D4   Dizemos que uma MT enigmática é fortemente enigmática se a linguagem aceita é enigmática.

D5   Dizemos que uma MT fortemente enigmática é canonicamente enigmática se for eficiente.

Para expressar D5 de outra maneira, toda linguagem enigmática é aceita por um conjunto de TMs de decisão criptograficamente canonicamente, que são as TMs de decisão mais eficientes que aceitam essa linguagem.

As perguntas feitas

A seguinte conjectura C0 é natural e (aparentemente) aberta:

C0   A classe de complexidade P contém pelo menos uma linguagem criptográfica.

São feitas três perguntas, Q1 - Q3 , das quais a primeira é:

Q1   A conjectura C0 é independente de PA ou ZFC?

Sob a suposição de que C0 é verdadeiro - provavelmente no ZFC, ou como um axioma independente que é complementar ao ZFC -, duas perguntas adicionais são naturais:

Q2   Pelo menos um idioma enigmático em P pode ser apresentado concretamente, ou seja, exibido como um dicionário de palavras explícitas em um alfabeto finito que inclui todas as palavras com o comprimento especificado? Nesse caso, exiba esse dicionário.

Q3   Pode pelo menos uma decisão canônica criptografada TM ser apresentada concretamente, ou seja, como uma descrição capacitadora para a construção de uma máquina de Turing física que decide (em tempo polinomial) todas as palavras do dicionário de Q2 ? Nesse caso, construa uma máquina de Turing e, computando com ela, exiba o dicionário de idioma enigmático de Q2 .

Considerações de definição

A definição D0 implica que todo número real gnóstico é computável, mas sabe-se que alguns números reais computáveis não são gnósticos. Para exemplos, consulte as respostas no MathOverflow de Michaël Cadilhac e Ryan Williams e no TCS StackExchange de Raphael Reitzig . De um modo mais geral, as definições D0 – D5 são criadas para excluir referências a expoentes de tempo de execução não gnóstico.

Conforme discutido no wiki do TCS " P contém linguagens incompreensíveis? ", As definições D0 a D5 garantem que toda linguagem criptográfica seja aceita por pelo menos uma TM que seja canonicamente criptográfica. (Observe também que, na presente pergunta, a palavra "enigmático" substitui a palavra menos descritiva "incompreensível" usada no wiki).

Além disso - em vista de D3 (a) e D3 (b)  - não existe uma redução computacionalmente trivial de uma MT canonicamente críptica para uma MT gnóstica que provavelmente reconhece o mesmo idioma. Em particular, D3 (a) e D3 (b) obstruem as estratégias de redução de polilimitros descritas nos comentários de Peter Shor e Sasho Nikolov , e independentemente por Luca Trevisan , além de obstruir também a estratégia de redução polinomialmente sincronizada de Timothy Chow , todos dos quais mascarar semelhante computações crípticos por sobreposição de uma computacionalmente supérfluo epi-cálculo .

Em geral, as definições de "gnóstico" e "enigmático" são deliberadamente ajustadas para serem robustas em relação a reduções matematicamente triviais (e é inteiramente possível que ajustes adicionais dessas definições sejam desejáveis).

Considerações metodológicas

A revisão de Lance Fortnow " O status do problema P versus NP " pesquisa métodos para estabelecer a independência (ou não) de conjecturas na teoria da complexidade; particularmente desejadas são sugestões de como os métodos que Lance revisa podem ajudar (ou não) a responder ao primeiro trimestre .

É claro que muitas outras perguntas são naturais. Por exemplo, a conjectura de Hartmanis-Stearns nos inspira a perguntar "Existem máquinas de Turing criptografadas em tempo real e criptografadas? Sua existência (ou não) é independente do PA ou do ZFC?"

Considerações do tipo Zeilberger

No caso de Q1 ser respondido com "sim", oráculos que decidem pertencer a existem fora do PA ou ZFC e, portanto, um elemento essencial da teoria moderna da complexidade (atualmente) não é conhecido por residir em qualquer sistema formal de lógica. P

Nesse aspecto, a teoria da complexidade se destaca da maioria das disciplinas matemáticas, de modo que as apreensões que Doron Zeilberger expressa em sua recente " Opinião 125: Agora que Alan Turing completou 100 anos de idade, é hora de dar uma nova olhada em suas contribuições seminais , que causou muitos benefícios, mas também muitos danos ", sem dúvida, são bem fundamentados.

As preocupações de Zeilberger assumem uma forma explícita como critério Z0    (! Q1  ) && (! C0  ), que é equivalente ao seguinte critério:

Z0:   Critério de sensibilidade de Zeilberger As   definições da classe de complexidade P   são chamadas de Zeilberger-sensível se todas as línguas em P são comprovadamente gnósticas.

Atualmente, não se sabe se a definição de Stephen P da classe de complexidade P   é sensível a Zeilberger.

Considerações motivacionais

As definições de "gnóstico" e "enigmático" são criadas com o objetivo de (eventualmente) decidir conjecturas como as seguintes:

C1   Seja e N P as restrições gnósticas de P e N P resp. Em seguida, P 'N P ' é demonstrável qualquer ou refutable em PA ou ZFE.PNPPNPPNP

C2   (como explicitamente provou em PA ou ZFE)PNP

Claramente C2   C1 , e, inversamente, é concebível que uma prova do (meta) teorema C1 possa fornecer orientação para uma prova do (mais forte) teorema C2 . 

A motivação geral é a expectativa / intuição / esperança de que, para alguma distinção bem sintonizada entre MTs e línguas gnósticas e enigmáticas, uma prova de C1 e possivelmente até C2 possa iluminar - e até ter implicações práticas comparáveis ​​a - uma presumivelmente muito mais difícil e profunda uma prova de que . PNP

Juris Hartmanis foi um dos primeiros teóricos da complexidade a perseguir seriamente essa linha de investigação; veja a monografia de Hartmanis, Feasible Computations e Provable Complexity Properties (1978), por exemplo.

Considerações nomenclaturais

Do Oxford English Dictionary (OED), temos:

  • gnóstico (adj)  Relacionado ao conhecimento; cognitivo; intelectual   "Eles [os números] existem de maneira vital, gnóstica e especulativa, mas não de maneira operativa".

  • criptográfico (adj)  Não é imediatamente compreensível; misterioso, enigmático   "Em vez de regras simples úteis para a humanidade, eles [filósofos] se opõem a cruptick e sentenças sombrias".

Aparentemente, nenhuma Revisão Matemática usou anteriormente a palavra "gnóstico" em qualquer sentido. No entanto, chama a atenção o artigo recente de Marcus Kracht “ Gnosis ” ( Journal of Philosophical Logic , MR2802332), que usa o sentido OED.

Aparentemente, nenhuma Revisão Matemática usou a palavra "enigmático" - em seu sentido técnico - com relação à teoria da complexidade. No entanto, chama a atenção o artigo de Charles H. Bennett " Profundidade lógica e complexidade física " (em The Universal Turing Machine: A Half-Century Survey , 1988), que contém a passagem

Outro tipo de complexidade associada a um objeto seria a dificuldade, dada o objeto, de encontrar uma hipótese plausível para explicá-lo. Objetos com esse tipo de complexidade podem ser chamados de "enigmáticos" : encontrar uma origem plausível para o objeto é como resolver um criptograma.

Considerações de naturalidade, abertura e dificuldade

A naturalidade dessas questões ilustra a tese da monografia de Juris Hartmanis, Feasible Computations and Provable Complexity Properties (1978), que:

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

A abertura e a dificuldade dessas perguntas são amplamente compatíveis com a conclusão da revisão de Lance Fortnow " O status do problema P versus NP " (2009) que:

"Nenhum de nós realmente entende o problema P versus NP, apenas começamos a descascar as camadas em torno dessa questão cada vez mais complexa".

Orientação da Wiki

Particularmente procurados são os ajustes de definição e estratégias de prova especificamente relacionados às questões Q1 – Q3 e que iluminam amplamente as conjecturas do tipo Hartmanis C1 – C2 .

John Sidles
fonte
Não sei o que você quer dizer no terceiro trimestre; parece que a representação de entrada influenciaria fortemente exatamente o que as TMs funcionam.
2
O que é um número real semidefinido positivo? Entendo "semidefinido positivo" para matrizes simétricas reais, mas o que isso significa para números !?
David Monniaux
Significa zero ou mais (um número visualizado como uma matriz 1x1).
precisa saber é o seguinte
1
linha de investigação interessante. Há muito tempo pensamos que a aceleração dos blums pode ter alguma conexão com perguntas como essa e / ou P =? NP, mas ainda não vimos isso pregado ou explorado em qualquer lugar. em particular, não vi uma prova muito rigoroso / rigoroso que não há nenhuma língua em P, que também está na classe identificada por Blum tal que o programa "não tem nenhum algoritmo mais rápido"
vzn
1
@JohnSidles Eu não acho que exista qualquer linguagem gnóstica dentro de P, mesmo que NP esteja contido em P. Talvez possamos separá-los como aqueles que podemos resolver pesquisando e os outros por um método diferente do que pesquisando.
Tayfun Pay

Respostas:

26

Eu acho que há uma dificuldade fundamental subjacente à pergunta que você está fazendo aqui (e que você fez na sua pergunta relacionada sobre idiomas incompreensíveis).

Grosso modo, parece que você está procurando um idioma tal queeu

faz, mas ZFC não sabem que L P .euPeuP

Para compreender as dificuldades com a sua pergunta, eu acho que você deve primeiro reconhecer que há uma diferença fundamental entre intensionais e extensionais definições de uma linguagem . Extensionalmente, L é determinado pelo que as palavras são ou não são membros da L . Ou seja, duas línguas L e L ' são extensionalmente iguais se, e somente se, contêm exatamente as mesmas palavras que os membros. Em contraste, um intensional definição de L descreve algumas condições para uma palavra para ser em L . Uma máquina de Turing que aceita Leueueueueueueueu, Ou uma fórmula de primeira ordem que é válida se e somente se X L , pode ser pensado como uma definição intensiva de L .ϕ(x)xeueu

O ponto é que todo que é (extensionalmente) em P admite uma descrição que é extremamente direta, porque P é a chamada classe de complexidade "sintática". Ou seja, basta usar uma máquina de Turing com clock polinomial , que termina exatamente na quantidade de tempo desejada. Qualquer sistema de "razoável" para a matemática fazendo, como a PA ou ZFC, vai ser capaz de provar que L P se você usar essa descrição simples de L .euPPeuPeu

Então, se você quer confundir ZFC, você vai ter que vir para cima com alguma descrição (intensional) de que é "muito complicado" para ZFC a reconhecer como sendo equivalentes à descrição direta de L . Isso é possível, mas, em certo sentido, é muito fácil ser interessante. Tudo o que você precisa fazer é pegar algo que sabemos que o ZFC não entende (por exemplo, sua própria consistência) e misturá-lo com a definição de L de alguma forma. Por exemplo, aqui está uma descrição de um conjunto de números inteiros:eueueu

é par e x não codifica uma prova de que o ZFC é inconsistente.xx

Supondo que o ZFC seja consistente, a fórmula acima define o conjunto de números pares, mas o ZFC não o conhece. Com um pouco mais mexer, podemos facilmente obter uma descrição do conjunto de inteiros pares que ZFC não será capaz de provar está em .P

O resultado é que, se você espera que o motivo seja difícil de provar que é que existem idiomas em P que são "muito complicados" para que possamos raciocinar, então acho que está latindo errado árvore. Extensionalmente, todo idioma em P está em P por razões triviais. Você pode enlamear as águas brincando com descrições impossivelmente opacas das línguas em P , mas esse é um truque geral que não tem nada a ver com P em particular, portanto, não acho que isso traga muitas informações.PNPPPPPP

Timothy Chow
fonte
Timothy, obrigado por este belo ensaio. Aprecio corretamente, no entanto, que a definição padrão de P - por complexidade computacional de Arora e Barak : uma abordagem moderna e / ou propriedades viáveis ​​e de complexidade de prováveis Hartmanis / Computations ou Provable Complexity , ou a declaração do Prêmio Millenium - NÃO é extensional? No entanto, talvez alguns problemas sejam mais tratáveis ​​se a definição de P for alterada adequadamente, com base em que (por Hartmanis) "Precisamos explorar ainda mais como nossa 'visão de mundo' da complexidade dos algoritmos deve ser alterada se considerarmos apenas possível propriedades dos algoritmos ".
John sidles
2
@JohnSidles, a definição padrão de P é "o conjunto de todos os idiomas que podem ser decididos por algum polytime TM". como uma linguagem é definida (intensional ou extensionalmente) não entra em cena: ela entra em cena apenas quando precisamos provar que alguma máquina em particular aceita alguma linguagem em particular.
Sasho Nikolov
1
Sasho, o impulso da resposta de Timothy Chow (como eu a li) é "Se definirmos P extensionalmente , então decidir se tornar membro de P é trivial". O impulso de seu comentário (como eu o li) é que, pela convenção atual, " P é definido intensionalmente ". A combinação dessas duas observações nos leva a apreciar a observação de Hartmanis: "Os resultados sobre a complexidade dos algoritmos mudam radicalmente se considerarmos apenas as propriedades dos cálculos que podem ser provadas formalmente". E assim nós naturalmente pergunto, como a definição de P pode ser variada, de modo a mais facilmente provar bons teoremas.
John sidles
1
@ John: Eu introduzi os termos "intensional" e "extensional" para fins expositivos. Os termos não são usados ​​formalmente em matemática. Em particular, não tenho certeza de que ajude a aplicar esses adjetivos à "definição padrão de ". No entanto, seu outro argumento, que explorar maneiras diferentes de definir P pode ser proveitoso, é com o que eu concordo. PP
Timothy Chow
Sim, as definições de gnóstico e transcendental são propostas com vistas a (eventualmente) provar declarações como as seguintes: Teorema Seja P ' e NP' as restrições gnósticas de P e NP resp. Então P '≠ NP' . Para uma definição adequadamente ampla e natural de "gnóstico", essa prova pode ser comparativamente esclarecedora e ter implicações práticas comparáveis ​​a uma prova (presumivelmente muito mais difícil?) De que P ≠ NP . AFAICT, Juris Hartmanis foi um dos primeiros teóricos da complexidade a perseguir seriamente essa linha de investigação.
John Sidles
8

Q1: Não
Q2: Sim, pelo menos dois-1s-em-binário


Lema: Toda TM com um expoente de tempo de execução computável que seja pelo menos 1 é transcendental.

Prova:
Seja A e B conjuntos recursivamente inseparáveis .M0 0M1Para qualquer máquina de Turing com calculável tempo de execução expoente r, quando r0 0,r1,r2,r3,...M0 0M1rmmUMA então a afirmação de D1 é verdadeira] e [se mB então a declaração de D1 é falsa]. Para qualquer máquina de Turing com expoente de tempo de execução computável r, quando r0 0,r1,r2,r3,...rmPortanto, a máquina de Turing é transcendental.


Definição:
pelo menos dois-1s-em-binário é o conjunto de números inteiros não negativos cuja
representação binária possui pelo menos dois 1s. (aposto que você nunca teria adivinhado ^ _ ^)

Definição:
M é a máquina de Turing que varre a representação binária de
sua entrada, aceita se encontrar pelo menos dois 1s e rejeita o contrário.

Obviamente, M decide pelo menos dois-1s-em-binário e possui expoente de tempo de execução 1, e nenhuma outra máquina de Turing com um expoente de tempo de execução menor também decide pelo menos dois-1s-em-binário.
Trivialmente,111Pelo lema, M é eficiente e transcendental.
Estes significam que pelo menos dois-1s-em-binário também é transcendental.

Portanto, TPCCC é um teorema de PA (e ZFC), e
pelo menos dois-1s-em-binário é uma linguagem transcendental concreta.


fonte
Ricky, muito obrigado! Levará alguns dias para contemplar sua engenhosa linguagem "pelo menos dois-1s-em-binário" (ALT1siB) e a MT que a aceita ... existem considerações de naturalidade que D1-5 são (esperançosamente) sintonizado para garantir e que (espero) o ALT1siB respeite. Especialmente procuradas são as intuições sobre "O que o ALT1siB nos ensina sobre complexidade?" Se você quiser fazer comentários a esse respeito, eles serão apreciados com gratidão.
John sidles
3
(Esperamos que você perceba isso, mas) A única coisa que estou usando no ALT1siB é que ele tem uma complexidade exatamente linear, para que não nos ensine nada sobre complexidade. O que o lema nos ensina é que a maioria das máquinas de Turing naturais é transcendental.
r . Isso corresponderia mais de perto a problemas práticos que surgem naturalmente na engenharia e equivale a perguntar "Existe uma definição natural de linguagens transcendentais?" o que é uma pergunta difícil.
John Sidles
Hmmm ... para colocar de outra maneira, já que nossa definição de transcendental é tão ampla que (pelo seu lema) até as MTs que nós (pensamos) entendemos bem - isto é, as MTs que consideramos como gnósticas - são de fato transcendental, a definição de "transcendental" precisa ser (espero que minimamente) restrita. Exemplo: desejamos respeitar nossa intuição de bom senso de que as MTs que decidem a primalidade através do teste de primalidade da AKS sejam gnósticas e não transcendentais. Sua resposta mostra que é necessário um ajuste de definição (provavelmente menor) ... mas o quê?
John sidles
1
Ricky, eu me pergunto se você se importaria de editar sua resposta para dar definições explícitas para m , s e t . Tal como está, as definições desses números precisam ser adivinhadas, e não estou confiante de que adivinhei corretamente. Em particular, entendo corretamente que a alteração de "real" para "racional" em D1 fecharia a brecha apontada por sua postagem (AFAICT), de modo que, no D1 alterado pelo menos algumas TMs são gnósticas?
John sidles
1

xn: =2+Eu=0 0n[1/2Eu E se Eu codifica uma prova de que ZF é inconsistente e 0, caso contrário]nxnxnx: =2+Eu=0 0[1/2Eu E se Eu codifica uma prova de que ZF é inconsistente e 0, caso contrário]

xZF

x>1MxnNsNs|s|x/registro(|s|)xMxMxMxMxO(|s|y)yxMx

xMxO(|s|2)x=2ZFZFZFMxZF+Con(ZF)

ZF+on(ZF)PZFO(|s|z)zZF

Mx

Ben Standeven
fonte
Ben, obrigado por esta resposta cuidadosamente fundamentada e cuidadosamente formulada. Levará alguns dias para digeri-lo ... Espero comentar em mais ou menos uma semana!
John Sidles