Problema computacional

Na ciência da teoria da computação, um problema computacional é um objeto matemático que representa um coleção de questões que computadores talvez queiram resolver. Por exemplo, o problema da fatoração

"Dado um inteiro positivo n, encontre um fator primo não-trivial de n."

é um problema computacional. Problemas computacionais são um dos principais objetos de estudo na ciência da teoria da computação. O campo de algoritmos estuda métodos de solução eficiente de problemas computacionais. O campo complementar de complexidade computacional tenta explicar porquê certos problemas computacionais são intratáveis por computadores.

Um problema computacional pode ser visto como uma coleção infinita de instâncias junto com uma solução para cada instância. Por exemplo, no problema da fatoração, as instâncias são os inteiros n, e as soluções são números primos p que descrevem fatores primos não-triviais de n.

É convencional representar ambas instâncias e soluções por strings binárias, a saber elementos de {0, 1}^*. Por exemplo, números podem ser representados como strings binárias usando-se codificação binária. (Para melhor leitura, identificamos números com suas codificações binárias nos exemplos abaixo.)

Tipos de problemas computacionais

Um problema de decisão é um problema computacional onde a resposta para cada instância é sim ou não. Um exemplo de um problema de decisão é o teste de primalidade:

"Dado um inteiro positivo n, determine se n é primo."

Um problema de decisão é tipicamente representado como o conjunto de todas as instâncias para as quais a resposta é sim. Por exemplo, o teste de primalidade pode ser representado pelo conjunto infinito

L = {2, 3, 5, 7, 11, ...}

Em um problema de busca, as respostas podem ser strings arbitrárias. Por exemplo, fatoração é um problema de busca onde as instâncias são (strings que representam) inteiros positivos e as soluções são (strings que representam) coleções de primos.

Um problema de busca é representado como uma relação consistindo em todos os pares instância-solução, chamada relação de busca. Por exemplo, primalidade pode ser representada pela relação

R = {(4, 2), (6, 2), (6, 3), (8, 2), (8, 4), (9, 3), ...}

a qual consiste em todos os pares de números (n, p), onde p é um fator primo não-trivial de n.

Um problema de contagem pede o número de soluções para um dado problema de busca. Por exemplo, o problema de contagem associado com primalidade é

"Dado um inteiro positivo n, conte o número de fatores primos não-triviais de n."

Um problema de contagem pode ser representado por uma função f de {0, 1}^* para o conjunto dos números inteiros não-negativos. Para uma relação de busca R, o problema de contagem associado a R é a função

f_R(x) = |{y: (x, y) ∈ R}|.

Um problema de otimização pede que seja achada a solução "melhor possível" dentre o conjunto de todas as possíveis soluções para um problema de busca. Um exemplo é o problema do máximo conjunto independente:

"Dado um grafo G, encontre um conjunto independente de G de tamanho máximo."

Problemas de otimização podem ser representados por suas relações de busca.

Problemas de promessa

Em teoria de complexidade computacional, é comumente assumido implicitamente que qualquer string em {0, 1}^* representa uma instância do problema computacional em questão. No entanto, algumas vezes, nem todas as strings {0, 1}^* representam instâncias válidas, e uma especifica um subconjunto adequado de {0, 1}^* como o conjunto das "instâncias válidas". Problemas computacionais desse tipo são chamados problemas de promessa.

O que vem a seguir é um exemplo de um problema de promessa (de decisão):

"Dado um grafo G, determine se cada conjunto independente em G tem tamanho de, no máximo, 5, ou G conjunto independente de tamanho de, pelo menos, 10."

Aqui, as instâncias válidas são aqueles grafos cujo tamanho de qualquer conjunto independente é no máximo 5 ou pelo menos 10.

Problemas de promessa de decisão são comumente representados como pares de subconjuntos disjuntos (L_sim, L_não) de {0, 1}^*. As instâncias válidas são aquelas em L_sim ∪ L_não. L_sim e L_não as instâncias cujas respostas são sim e não, respectivamente.

Problemas de decisão exercem um papel importante em diversas áreas da complexidade computacional, incluindo dificuldade de aproximação, teste de propriedade, e sistemas de provas interativas.

Referências

• Even, Shimon; Selman, Alan L.; Yacobi, Yacov (1984), «The complexity of promise problems with applications to public-key cryptography», Information and Control, 61 (2): 159–173, doi:10.1016/S0019-9958(84)80056-X .
• Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, ISBN 978-0-521-88473-0, Cambridge University Press .
• Goldreich, Oded; Wigderson, Avi (2008), «IV.20 Computational Complexity», in: Gowers, Timothy; Barrow-Green, June; Leader, Imre, The Princeton Companion to Mathematics, ISBN 9780691118802, Princeton University Press, pp. 575–604 .