Qual é a diferença entre um algoritmo, uma linguagem e um problema?

Parece que neste site, as pessoas geralmente corrigem outras por "algoritmos" e "problemas" confusos. Qual é a diferença entre estes? Como sei quando devo considerar algoritmos e problemas? E como eles se relacionam com o conceito de linguagem na teoria formal da linguagem?

Para simplificar, começarei considerando apenas os problemas de "decisão", que têm uma resposta sim / não. Os problemas de função funcionam aproximadamente da mesma maneira, exceto em vez de sim / não, há uma palavra de saída específica associada a cada palavra de entrada.

Idioma : um idioma é simplesmente um conjunto de strings. Se você possui um alfabeto, como , é o conjunto de todas as palavras que contêm apenas os símbolos em . Por exemplo, é o conjunto de todas as seqüências binárias de qualquer tamanho. Um alfabeto não precisa ser binário, no entanto. Pode ser unário, ternário, etc.Σ ∗ Σ { 0 , 1 } $\Sigma$$\Sigma^*$$\Sigma$$\{0,1 \}^*$

Um idioma sobre um alfabeto é qualquer subconjunto de .Σ $\Sigma$$\Sigma^*$

Problema : Um problema é uma pergunta sobre alguma entrada que gostaríamos de responder. Especificamente, um problema de decisão é uma pergunta que pergunta: "Nossa entrada fornecida preenche a propriedade ?$X$

Uma linguagem é a realização formal de um problema. Quando queremos raciocinar teoricamente sobre um problema de decisão, geralmente examinamos o idioma correspondente. Para um problema , o idioma correspondente é:$X$

y X y X $L = \{w \mid w$ é a codificação de uma entrada para o problema , e a resposta para a entrada para o problema é "Yes" $y$$X$$y$$X$$\}$

Determinar se a resposta para uma entrada para um problema de decisão é "yes" é equivalente a determinar se uma codificação dessa entrada sobre um alfabeto está no idioma correspondente.

Algoritmo : Um algoritmo é uma maneira passo a passo de resolver um problema. Observe que um algoritmo pode ser expresso de várias maneiras e várias linguagens, e que existem muitos algoritmos diferentes para resolver qualquer problema.

Máquina de Turing : Uma máquina de Turing é o análogo formal de um algoritmo. Uma máquina de Turing sobre um determinado alfabeto, para cada palavra, irá ou não parar em um estado de aceitação. Assim, para cada máquina de Turing , existe um idioma correspondente:$M$

w $L(M) = \{w \mid M$ pára em um estado de aceitação na entrada .$w\}$

(Há uma diferença sutil entre as máquinas de Turing que param em todas as entradas e nas entradas yes, que define a diferença entre as classes de complexidade e .)R $\mathsf{R}$$\mathsf{RE}$

A relação entre idiomas e máquinas de Turing é a seguinte

1. Toda máquina de Turing aceita exatamente um idioma

2. Pode haver mais de uma máquina de Turing que aceita um determinado idioma

3. Pode não haver uma máquina de Turing que aceite um determinado idioma.

Podemos dizer aproximadamente a mesma coisa sobre algoritmos e problemas: todo algoritmo resolve um único problema, mas pode haver 0, ou muitos, algoritmos resolvendo um determinado problema.

Complexidade do tempo : Uma das fontes mais comuns de confusão entre algoritmos e problemas é em relação às classes de complexidade. A alocação correta pode ser resumida da seguinte forma:

• Um algoritmo tem uma complexidade de tempo
• Um problema pertence a uma classe de complexidade

Um algoritmo pode ter uma certa complexidade de tempo. Dizemos que um algoritmo tem uma complexidade limite superior, no pior caso, se o algoritmo parar no máximo em etapas para qualquer entrada do tamanho .f ( n ) $f(n)$$f(n)$$n$

Os problemas não têm tempos de execução, pois um problema não está vinculado a um algoritmo específico que realmente é executado. Em vez disso, dizemos que um problema pertence a uma classe de complexidade, se existir algum algoritmo que resolva esse problema com uma dada complexidade de tempo.

P X X P X X $\mathsf{P}, \mathsf{NP}, \mathsf{PSPACE}, \mathsf{EXPTIME}$ etc. são todas classes de complexidade. Isso significa que eles contêm problemas, não algoritmos. Um algoritmo nunca pode estar em , mas se houver um algoritmo de tempo polinomial resolvendo um determinado problema , estará em . Também pode haver um monte de algoritmos de tempo exponencial que aceitam , mas como existe um único algoritmo de tempo polinomial que aceita , ele está em .$\mathsf{P}$$X$$X$$\mathsf{P}$$X$$X$$\mathsf{P}$