Perguntas com a marcação «decidability»

Problema: Considere um número finito de estados de controle (incluindo um estado "inicial" e "ruim"), um número finito de variáveis ​​inteiras e, para cada par de estados ordenados, uma relação de transição expressa na aritmética de Presburger. Decida se existe um invariante indutivo (= estável...

Resposta Aceita A resposta de Scott Aaronson foi "aceita" (principalmente porque é a única resposta!) Resumo de uma frase da resposta As   generalizações plausivelmente naturais da questão P versus NP não são obviamente mais fáceis de resolver do que P versus NP em si. Uma obstrução a uma...