Por que usar linguagens na teoria da complexidade

Estou apenas começando a entrar na teoria da computação, que estuda o que pode ser calculado, com que rapidez, usando quanta memória e com qual modelo computacional.

Eu tenho uma pergunta bem básica, mas realmente espero que alguns de vocês possam me ajudar a entender o conceito por trás disso:

Por que tudo está centrado na noção e definição de IDIOMAS (ou seja, linguagens regulares e linguagens livres de contexto)? E como eles se relacionam e descrevem a complexidade de um algoritmo e os possíveis modelos computacionais para resolvê-los?

Eu li esses tipos de perguntas relacionadas:

• /cstheory/14811/what-is-the-enlightenment-im-supposed-to-attain-after-studying-finite-automata
• /cstheory/8539/how-practical-is-automata-theory

mas ainda não tenho uma resposta para minhas dúvidas, pois elas fornecem uma justificativa prática de por que são importantes (o que eu entendo), mas não me ajudam a entender por que a teoria da complexidade se baseia nelas.

É porque as línguas são a melhor (apenas?) Maneira de formalizar o conceito de "problema".

Um algoritmo (Turing Machine) tem desempenho, que expressamos através da complexidade do grande O. Um problema (idioma) pertence a uma classe de complexidade. Estes são geralmente definidos pela existência: se existe uma máquina que aceita uma linguagem que é executada em determinado desempenho (espaço ou tempo), a linguagem pertence à classe de complexidade correspondente.$L$

Existem algumas razões para isso. O primeiro é que os idiomas são independentes de plataforma. Você não está preocupado se um número inteiro é 32 ou 64 bits ou se as operações de ponto flutuante são executadas em paralelo com outras operações. Essas coisas aumentam o desempenho no nível micro, mas a análise da complexidade está interessada no nível macro. À medida que você escala de 100 a a a entradas, como o desempenho do algoritmo muda? Passa do uso de 1 milhão de células de fita para 1 bilhão, ou de 1 milhão para mais células do que existem átomos no universo?10 9 10 $10^6$$10^9$$10^{12}$

A segunda é que as linguagens são apenas uma boa abstração para os dados. Você precisa de algo sobre o qual possa fazer provas, algo que possa modelar formalmente. Codificar sua entrada e saída como uma string significa que agora você está lidando não com bits na memória, mas com objetos matemáticos com propriedades específicas. Você pode argumentar sobre eles e provar provas sobre eles em um sentido formal e muito simples.

A teoria da complexidade tende a se concentrar nos problemas de decisão porque eles acabam sendo difíceis. Quando a versão de decisão do vendedor ambulante é NP-completa (ou seja, existe um passeio menor que o comprimento ), é óbvio que encontrar o caminho mais curto é mais difícil. Não há tanto foco nos problemas de função / otimização porque ainda há muitas perguntas em aberto e problemas não resolvidos sobre os problemas de decisão mais simples.$k$

Acho que aqui está o meu desafio para você: encontre uma maneira de descrever matematicamente problemas que não são idiomas. Não sei se os idiomas são especiais, mas acho que eles são a ferramenta mais simples que temos, a mais fácil de lidar.

Existem duas respostas básicas para sua pergunta:

1. Há mais na teoria da complexidade do que nas linguagens, por exemplo, classes de funções, complexidade aritmética e as subáreas de algoritmos de aproximação e inadequação.

2. Razões históricas: um dos artigos básicos da teoria da computabilidade discutia o Entscheidungsproblem de Hilbert (uma forma do problema da parada).

Infelizmente, não sei muito sobre o último, mas deixe-me expandir sobre o primeiro.

Complexidade além das línguas

Toda classe de complexidade computacional vem com uma classe de função associada . Por exemplo, a classe P de todos os problemas decidíveis em tempo polinomial está associada ao FP, a classe de todas as funções computáveis ​​em tempo polinomial. FP é importante, uma vez que é utilizado para definir NP-dureza: uma língua é NP-se difícil para cada idioma em NP existe uma função em FP tais que sse . Outra classe de funções de complexidade, #P , está relacionada à chamada hierarquia polinomial via teorema de Toda .M f M x ∈ M f M ( x ) ∈ $L$$M$$f_M$$x \in M$$f_M(x) \in L$

A complexidade do circuito aritmético (ou teoria da complexidade algébrica ) lida com a complexidade da computação de vários polinômios. As classes de complexidade importantes aqui são VP e VNP, e a teoria da complexidade geométrica é um projeto importante que tenta separar VP e VNP (e posteriormente P e NP) usando a geometria algébrica e a teoria da representação.

Outro exemplo importante de complexidade algébrica é a multiplicação rápida de matrizes. Aqui a questão básica é com que rapidez podemos multiplicar duas matrizes ? Perguntas semelhantes perguntam com que rapidez podemos multiplicar números inteiros, com que rapidez podemos testar a primalidade de números inteiros (este é um problema de decisão!) E com que rapidez podemos fatorar números inteiros.

A otimização convexa lida com problemas de otimização que podem ser resolvidos (ou quase resolvidos) com eficiência. Exemplos são programação linear e programação semidefinida, ambos com algoritmos eficientes. Aqui estamos interessados ​​tanto na solução ótima quanto na própria solução ideal. Como geralmente há mais de uma solução ótima, o cálculo de uma solução ótima não é bem representado como um problema de decisão.

Aproximabilidade é a área que estuda quão boa podemos obter para um problema de otimização em tempo polinomial. Considere, por exemplo, o problema clássico da cobertura de conjuntos: dada uma coleção de conjuntos, quantos deles precisamos para cobrir todo o universo? Encontrar o número ideal é difícil para o NP, mas talvez seja possível calcular uma aproximação? Algoritmos de aproximação é a subárea que estuda algoritmos para calcular aproximações, enquanto a inadequação estuda os limites dos algoritmos de aproximação. No caso específico de Set Cover, temos um algoritmo que fornece uma aproximação (o algoritmo ganancioso) e é difícil para o NP fazer melhor.$\ln n$

Vejamos essa questão da perspectiva da teoria das categorias. Os problemas de decisão (ou idiomas) corresponderiam aos objetos de uma categoria e as reduções permitidas entre dois problemas corresponderiam aos morfismos (setas) de uma categoria.

Falar sobre idiomas tem a vantagem de que a equivalência de idiomas está bem definida (nomeadamente pela igualdade extensional). Dois problemas não relacionados podem levar ao mesmo idioma e, em seguida, podemos considerá-los como equivalentes. Se quisermos falar sobre problemas isomórficos, teremos que definir os morfismos permitidos entre dois problemas. Mas os morfismos permitidos dependem da classe de complexidade real em consideração, o que torna essa abordagem menos adequada para comparar diferentes classes de complexidade.

A noção de problemas isomórficos será normalmente mais grossa que a noção de idiomas equivalentes, ou seja, dois problemas podem ser isomórficos, mesmo que seus idiomas associados não sejam equivalentes. O pior é que muitas vezes existem noções razoáveis ​​diferentes para os morfismos permitidos, que apenas concordam com relação aos isomorfismos permitidos. O foco nos idiomas permite adiar esses problemas até que tenhamos vontade de falar sobre algumas noções razoáveis ​​diferentes de redução (como redução de Karp x redução de Cook).