7

Comecei a ler sobre teoria da computação e me deparei com os "problemas de decisão".

O que são estes problemas?

Não quero nenhum artigo cientifico altamente elaborado para responder a pergunta, só uma visão rápida de o que é isto e como pode ser representado.

0

2 Respostas 2

7

Sendo breve e sucinto um problema de decisão é um tipo especial de problema computacional que resposta é sim ou não, ou alternativamente 1 ou 0.

EDITADO Resposta menos sucinta:

Qualquer coisa que você possa representar como uma função que receba um parâmetro e tem como resposta um booleano exemplo:

A entrada é um grafo arbitrário. O problema consiste em decidir se o dado grafo é conexo ou não. A linguagem formal associada a este problema de decisão é então o conjunto de todos os grafos conexos—obviamente, para obter uma definição precisa dessa linguagem, é preciso decidir como grafos são codificados como cadeias binárias. Fonte

4
  • Consegue ser um pouco menos sucinto? Por exemplo, toda e qualquer expressão booleana, em que os possíveis resultados são true e false, são classificadas como problema de decisão?
    – Woss
    Commented 28/07/2017 às 12:46
  • Significa que pode assumir os dos estados ao mesmo tempo 0 e 1?
    – gato
    Commented 28/07/2017 às 12:47
  • Como eu respondi 0 OU 1, não 0 E 1. Commented 28/07/2017 às 12:55
  • @gato isso é uma coisa quântica. Problemas de decisão quânticos retornam um qubit, porém o qubit só permanece nesse estado enquanto não for avaliado por um sistema externo; tipo, máquinas quânticas retornam qubits apenas para outras máquinas quânticas. A propósito, um qubit é a sobreposição entre true e false, o que significa que algo pode ser 73% verdade é 27% falso, não apenas meio a meio Commented 5/09/2017 às 12:34
6

O Um Programador está certo na resposta dele.

Eu fiquei curioso e fui atrás de mais material. Encontrei isso na Wikipedia:

Na teoria da computabilidade e na teoria da complexidade computacional um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não. Por exemplo, o problema: "dados dois números x e y, y é divisível por x?" é um problema de decisão. (...)

Então, para todos os fins práticos, a gente pode interpretar isso como "qualquer coisa que você possa representar com uma função/método que considere uma condição e retorna booleano".

Na verdade existem muitas implicações sobre isso para quem estuda matemática cientificamente, ou para quem faz pesquisa sobre a história da computação. Mas para a maioria de nós acaba por ser apenas uma curiosidade.

P.s.: isso não quer dizer que isso não seja de grande importância. Alan Turing desenvolveu todo seu trabalho sobre máquinas de computar para resolver problemas como o problema de decisão. Se esses problemas não tivessem sido propostos, nós não teríamos toda a tecnologia que temos hoje.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .