Um problema simples cuja decisão não é conhecida

92

Estou me preparando para uma palestra voltada para alunos de graduação em matemática e, como parte disso, estou pensando em discutir o conceito de decidibilidade. Quero dar um exemplo de um problema que atualmente não sabemos ser decidível ou indecidível. Existem muitos desses problemas, mas nenhum parece se destacar como bons exemplos até o momento.

O que é um problema simples de descrever cuja decisão está aberta?

Lev Reyzin
fonte
26
O Problema de Collatz é um problema simples de descrever, cuja decisão é aberta. Uma generalização do problema de Collatz mostrou-se indecidível. math.mit.edu/~poonen/papers/sampler.pdf mathworld.wolfram.com/CollatzProblem.html
Mohammad Al-Turkistany
2
Talvez você também possa mostrar esse belo "truque": escreva um pequeno programa (você pode chamá-lo de "goldbach") que itera pelos números pares e verifica se n i = p j + p k para alguns primos p j , p k < n i e para no caso negativo ... depois diga "bem, não sabemos se o problema de parada para este programa é decidível!" :-). Mostra a forte correlação entre os problemas da teoria dos números e o problema da parada. nEu5nEu=pj+pkpj,pk<nEu
Marzio De Biasi
8
Isso parece bom, mas o conceito de decidibilidade não se aplica apenas a uma instância específica, pois, para ambos os casos, a resposta é apenas um sim / não fixo.
Lev Reyzin
6
@MarzioDeBiasi, essa não é uma "forte correlação" entre o problema da parada e a teoria dos números. Qualquer conjectura da forma "widgets frangíveis não existem" pode ser transformada em um programa que interrompe se houver um widget frangível, desde que a frangibilidade seja decidida e os widgets sejam recursivamente enumeráveis. A existência desse programa é apenas o elo mais trivial entre o problema da parada e a teoria dos widgets.
David Richerby
2
@ DavidRicherby: bastante convincente :-). Eu estava apenas tentando destacar o fato (surpreendente para mim) de que resolver o problema da parada por alguns bits de código corresponde à solução de uma conjectura matemática de longa data. Então eu deveria substituir "forte correlação" com "correlação fraca, mas surpreendente para mim" :-) :-)
Marzio De Biasi

Respostas:

91

O problema da mortalidade matricial para matrizes 2x2. Ou seja, dada uma lista finita de 2x2 matrizes inteiras M 1 , ..., M k , pode o M i ser multiplicados em qualquer ordem (com arbitrariamente muitas repetições) para produzir a matriz com 0?

(O caso 3x3 é conhecido por ser indecidível. O caso 1x1, é claro, é decidível.)

Scott Aaronson
fonte
6
epubs.siam.org/doi/abs/10.1137/1.9781611974782.12 Igor Potapov e Pavel Semukhin mostraram recentemente que isso é decidível.
Chao Xu
4
@ChaoXu: Esse artigo parece ser apenas para matrizes não-singulares .
2
@RickyDemer Você está correto, meu erro.
Chao Xu
57

ATUALIZAÇÃO: O problema que mencionei aqui agora é conhecido por ser indecidível! http://arxiv.org/abs/1605.05274 Além disso, o artigo foi inspirado pela leitura desta mesma resposta. :)


Os programadores do seu público-alvo principal de matemática podem se surpreender ao saber que a pergunta "esse tipo é implicitamente conversível nesse tipo?" não é conhecido por ser decidido em nenhum dos Java 5, C # 4 e Scala 2.

Para mais detalhes, consulte o artigo de Andrew Kennedy e Benjamin Pierce "Sobre a decidibilidade da subtipagem nominal com variação" . O artigo fornece alguns exemplos de restrições adicionais aos sistemas de tipos dessas linguagens, sob as quais a subtipagem nominal se torna decidível ou indecidível.

Curiosamente, o artigo foi escrito bem antes da covariância e contravariância genéricas serem adicionadas ao C #, mas os autores anteciparam corretamente a direção que o idioma estava seguindo. (Isso não é surpreendente; os autores criaram o suporte subjacente à variação no CLR, do qual eu aproveitei ao adicionar variação ao C #! Eles fizeram o trabalho pesado.)

Eric Lippert
fonte
7
@ vzn: O compilador Microsoft C # pode ser feito para entrar em uma recursão ilimitada. Veja meu artigo sobre o assunto: blogs.msdn.com/b/ericlippert/archive/2008/05/07/…
Eric Lippert
3
@vzn: Existem maneiras de fazer com que o compilador Java também se comporte mal, mas não conheço os detalhes.
quer
2
A linguagem de tipos do @vzn Scala é Turing completa e, portanto, o verificador de tipos do Scala pode fazer um loop. Veja aqui para detalhes. O mesmo vale para Haskell . Não tenho familiaridade suficiente com C # e Java para saber se é possível fazer com que os respectivos revisores de tipos façam um loop.
Martin Berger
3
@vzn: Isso também pode ser interessante para você: a resolução de sobrecarga no C # 3 é pelo menos NP-HARD, porque você pode forçar o compilador a resolver problemas arbitrários de SAT: blogs.msdn.com/b/ericlippert/archive/2007/03 / 28 /…
Eric Lippert 07/10
7
@vzn: Finalmente, a pergunta "isso é um pouco acadêmica?" é claro que respondeu sim. A pergunta "blá é conhecida por ser decidível?" é, por natureza, uma questão acadêmica. Esses casos não surgem no código realista da linha de negócios. A importância desta questão do ponto de vista da engenharia está na segurança ; um terceiro hostil pode fornecer código onde analisá-lo antes de executá-lo pode causar mau comportamento? Essa é a situação em que estamos na internet, onde terceiros hostis enviam JavaScript para o seu navegador.
precisa
47

O décimo problema de Hilbert sobre os racionais: "Essa equação polinomial tem uma solução racional?"

Boris Bukh
fonte
1
Obrigado - você tem um link para algum lugar que diz que está aberto?
Lev Reyzin
1
Veja www-math.mit.edu/~poonen/papers/subrings.pdf (segundo parágrafo). Há também um artigo expositivo em www-math.mit.edu/~poonen/papers/aws2003.pdf
Boris Bukh
também seria útil ver uma descrição de esboço / estrutura de tópicos por que esse problema não é equivalente ao 10º problema de Hilberts e a mesma prova não se aplica.
vzn
2
vzn: Equações sobre racionais podem ser vistas como um caso especial de equações sobre números inteiros (multiplicando para limpar os denominadores). Portanto, a questão é se esse caso especial do décimo problema de Hilbert já é indecidível. As equações diofantinas produzidas pelas provas existentes não têm a forma especial necessária.
Scott Aaronson
1
@vzn Uma razão pela qual é sutil é que a maioria (talvez todas) das estratégias de prova violaria a Conjectura de Mazur. Veja a página 1 do primeiro link de Boris Bukh para obter mais informações.
David E Speyer
23

Um problema simples cuja decidibilidade é desconhecida é o seguinte (acho que ainda está aberto):

Xadrez infinito :

Entrada : Uma lista finita de peças de xadrez e suas posições iniciais em um tabuleiro de xadrez; Pergunta : O branco pode forçar o acasalamento?Z×Z

Se adicionarmos a restrição de que as brancas devem acasalar em movimentos ( n faz parte da entrada), torna-se decidível: veja Dan Brumleve, Joel David Hamkins e Philipp Schlicht. .nn


Outro problema simples é o comportamento da formiga de Langton na configuração inicial finita.

O comportamento das formigas de Langton com suporte finito :

Os quadrados de um avião são coloridos de várias formas em preto ou branco. Arbitrariamente identificamos um quadrado como a "formiga". A formiga pode viajar em qualquer uma das quatro direções cardeais a cada passo que der. A formiga se move de acordo com as regras abaixo:

  • Em um quadrado branco, vire 90 ° para a direita, vire a cor do quadrado, avance uma unidade
  • Em um quadrado preto, vire 90 ° para a esquerda, vire a cor do quadrado, avance uma unidade

Entrada : uma configuração finita (preto / branco) do plano e da posição da formiga;
Pergunta : A formiga sempre termina de construir uma "estrada" infinita recorrente?

insira a descrição da imagem aqui

Para suporte infinito, o problema é indecidível, veja: A. Gajardo, A. Moreira e E. Goles, Complexidade da formiga de Langton

Marzio De Biasi
fonte
20

O Problema de Collatz é um problema simples de descrever, cuja decisão é aberta. Envolve uma simples recorrência de operações aritméticas elementares.

f(n)={ n/23n+1

n0 0

Curiosamente, uma generalização do problema de Collatz mostrou-se indecidível.

Referências:

1- PROBLEMAS INDECIDÁVEIS: UM AMOSTRAGEM, POÇOS DE BJORN

2- Weisstein, Eric W. "Problema de Collatz". De MathWorld - um recurso da Web da Wolfram.

3- O Problema 3X + 1: Uma Visão Geral , Jeffrey C. Lagarias

Mohammad Al-Turkistany
fonte
13
A rigor, a resposta para sua pergunta específica é simplesmente "sim" ou "não", portanto não pode ser indecidível. Por outro lado, saber se um número específico é um número de Collatz pode ser indecidível.
Lev Reyzin
@LevReyzin Thanks. Editado para corrigir o problema.
Mohammad Al-Turkistany
feliz que esta resposta esteja agora incluída e sugira que todos os outros problemas importantes da teoria dos números abertos possam ser formulados de maneira semelhante a outros comentários / respostas e pense que esse elo fundamental está próximo de um teorema da ponte central inexplorado pelas comunidades teóricas.
vzn
estudo de Collatz conjectura a partir de um mais ângulo TCS / empírica com muitas referências aqui (por exemplo, através EFM transdutor recursão , sistema de marcação , etc)
vzn
16

A decidibilidade da contenção de consultas em conjunto está aberta há mais de vinte anos. Resolver isso seria um avanço na teoria do banco de dados.

Q1Q2Q1EuQ2Eu

Nas consultas conjuntivas, usa-se AND para vincular predicados quantificados existencialmente. Em termos SQL, as consultas conjuntivas são as consultas SELECT-FROM-WHERE usando "=" e "AND", mas sem subconsultas ou agregação. Esse talvez seja o tipo mais comum de consulta ao banco de dados e inclui a maioria das consultas de mecanismos de pesquisa.

EuQ1Q2

(N,+,×)(N,+,×)

Para indicações sobre a extensa literatura e um tratamento rigoroso, consulte um documento do ToDS (no prelo) de algumas pessoas.

QRQQ E RQ

András Salamon
fonte
Aqui está um artigo relacionado .
Martin Berger
1
@MartinBerger: A versão ToDS inclui a prova de dureza NP mencionada acima, tem provas completas e é de acesso aberto (embora omita o material sobre uniões de CQs devido à falta de espaço). dx.doi.org/10.1145/2556524
András Salamon
15

Problema de correspondência do Post com um número fixo de peças entre 3 e 6.

Embora não seja realmente simples de descrever, ele tem uma descrição muito "divertida", e acho adequada para conversas em nível de intuição.

Shaull
fonte
13

O problema generalizado da altura das estrelas: "quantos ninhos de estrelas Kleene eu preciso para representar essa linguagem regular, com uma expressão regular com complementação permitida?"

Nem sabemos se o algoritmo que sempre retorna 1 (exceto 0 para idiomas sem estrelas, que é um caso decidível) está correto.

Denis
fonte
10

Um problema da teoria de autômatos.

D

xDxxeu(D)PrEumes

Comentários: Eu ouvi esse problema originalmente em uma resposta de stackexchange de Jeffrey Shallit. Se você souber de alguma referência, informe-me. Obrigado!

Mensagens Relacionadas:

(1) Ainda há problemas em aberto nos DFAs?

(2) https://cs.stackexchange.com/questions/48084/determining-if-infinite-binary-language-dfas-contain-at-least-1-prime

Trabalho relacionado: https://cs.uwaterloo.ca/~shallit/Papers/br10.pdf

"Elementos mínimos para os números primos" de C. Bright, R. Devillers e J. Shallit

Michael Wehar
fonte
7

Mapas iterados no intervalo (descrição daqui ):

(muito relacionado ao problema proposto por Magnus Find)

FxxxF(x)F(F(x))FxF

Fxyxy

F

FxyxF

Uma referência: Asarin 2011 .

Nicolas Perrin
fonte
2

parece haver uma maneira / ângulo bastante natural de estudar essa questão, que é utilizada em pelo menos três trabalhos, como segue.

TM(k,l)keuk,euk,eu

os resultados podem ser exibidos em uma grade como em algumas das refs a seguir. Também na região intermediária, é sabido que algumas máquinas (não resolvidas) são capazes de simular a conjectura de Collatz para algumas entradas.

portanto, há claramente um "ponto de transição" como fenômenos operando aqui, mas não dentro de uma região computável, mas em um sentido incomum entre computável e não computável.

vzn
fonte
ps o De Mol ref pdf não foi para download para mim do arXiv, no momento da escrita, ele trava
vzn
-10

existe uma maneira bastante natural de mapear a maioria dos problemas abertos para questões de (in) decidibilidade. a maioria dos problemas abertos geralmente não é comprovada ou comprovada.

na web, existe alguma confusão informal sobre a indecidibilidade do problema P vs NP , que não é estritamente um problema de decisão; portanto, falar sobre sua indecidibilidade não é tecnicamente correto. mas, por outro lado, parece haver um vínculo próximo / natural entre indecidibilidade e provabilidade, como segue.

por exemplo, considere

euxO(nx)

esse idioma é decidível? essa é uma pergunta sobre uma linguagem com sua decidibilidade aberta que está basicamente intimamente ligada (até, virtualmente idêntica) ao problema P vs NP e à sua provabilidade inerente (in?).

quanto a P vs NP como "simples de descrever", requer apenas conceitos de TMs , notação de tempo de execução Big O , não determinismo , que são razoavelmente simples (alguns dos conceitos mais básicos do TCS) e ensinados no nível de graduação ou que são talentosos estudante do ensino médio poderia entender.

de fato, NP vs P / Poly também é aberto e pode ser mapeado para uma pergunta aberta sobre decidibilidade da mesma maneira, e isso pode ser afirmado como um problema bastante simples sobre o crescimento de circuitos mínimos (monótonos?) para reconhecer NP completo problemas (por exemplo, panelinhas).

vzn
fonte
3
euxeu=xΘ(nx)eueu
2
dizer que um número inteiro é incontestável não faz sentido. e não acho que o princípio do meio excluído seja afetado pela comprovação da afirmação.
Sasho Nikolov 05/09
5
corrija sua resposta ou pare de deixar comentários. Eu já vi essas perguntas, mas se você não conseguir usá-las ou as respostas dadas para corrigir sua própria bagunça completa de resposta, ou, pior ainda, se você não quiser, talvez deva procurar outra comunidade.
Sasho Nikolov 19/09/2013
5
direto ao ponto, o problema em sua resposta é trivialmente decidível, independentemente da resolução ou independência formal do problema P vs NP do ZFC. além disso, criar problemas que são possivelmente indecidíveis ou trivialmente decidíveis, dependendo da verdade de uma conjectura famosa, nada mais é do que um exercício atraente (no qual você até agora falha completamente), e na maioria dos casos não mostra nada sobre a dificuldade intrínseca de uma conjectura .
Sasho Nikolov 19/09/2013