Análise da Complexidade de Espaço em Algoritmos

COMPLEXIDADE DE ESPAÇO Pedro Paulo Balbi versão 12052023 Além da análise de complexidade de tempo que visa estudar o custo temporal dos algoritmos também é possível realizar uma análise de complexidade no espaço isto é considerando quanto de memória algoritmos necessitam Por analogia ao que estudamos sobre complexidade de tempo fica muito mais fácil estudar complexidade de espaço Seja M uma Máquina de Turing Determinística que para sobre todas a entradas A complexidade de espaço de M é a função f N N onde fn é o número máximo de células de fita que M visita considerandose qualquer entrada de comprimento n Complexidade de espaço de M é fn º M roda em espaço fn De forma análoga se M é uma Máquina de Turing NãoDeterminística na qual todas as suas cópias param sobre todas as entradas definimos sua complexidade de espaço fn como o número máximo de células de fita que M visita considerando cada ramo individual de computação para qualquer entrada de comprimento n A partir das duas definições acima caracterizamse as seguintes classes de complexidade de espaço SPACEfn L L é uma linguagem decidida por uma Máquina de Turing Determinística de espaço Ofn NSPACEfn L L é uma linguagem decidida por uma Máquina de Turing NãoDeterminística de espaço Ofn Exemplo 83 de Sipser 2013 O problema SAT pode ser resolvido com um algoritmo de espaço linear ie SPACEn Teorema de Savitch Para qualquer função f N Â onde fn ³ n NSPACEfn Í SPACE f 2n OBS Conforme Sipser 2013 p351 o teorema também vale sempre que fn ³ Logn Por analogia à classe P definese a classe PSPACE como a classe de linguagens que são decidíveis em espaço polinomial por uma Máquina de Turing Determinística De modo semelhante à classe NP definese a classe NPSPACE que é a classe de linguagens que são decidíveis em espaço polinomial por uma Máquina de Turing não Determinística Pelo Teorema de Savitch temse que NPSPACE Í PSPACE já que o quadrado de um polinômio continua sendo um polinômio Mas como toda DTM também é uma NDTM então PSPACE Í NPSPACE Isso é análogo ao fato de que P Ì NP Logo PSPACENPSPACE Eis um diagrama resumindo no que se acredita atualmente onde Observese que as classes de complexidade de tempo e de espaço não são independentes Leiase por exemplo Todo problema que pode ser resolvido polinominalmente também pode ser resolvido exponencialmente mas não necessariamente o contrário Ainda de forma análoga aos conceitos de complexidade de tempo definese 1 Uma linguagem B é PSPACEcompleta se ela satisfaz duas condições a B Î PSPACE b Toda linguagem A em PSPACE é redutível em tempo polinomial a B 2 Se a linguagem B satisfaz somente à condição b acima dizemos que B é PSPACEdifícil ou PSPACEhard OBS Para provar que linguagens são dos tipos acima também utilizamos um processo de redução dessas linguagens à linguagem conhecida Mas surpreendentemente ainda lançamos mão de uma redução em tempo polinomial apesar de estarmos tratando de complexidade de espaço Informalmente isso se deve à necessidade de ainda termos de ser capazes de realizar uma redução eficiente Ver discussão no início da Seção 83 PSPACECompleteness pp 337338 de Sipser 2013 Sabemos que fórmulas Booleanas podem conter quantificadores existencial e universal Fórmulas Booleanas com quantificadores são chamadas de fórmulas Booleanas quantificadas Quando todas as variáveis de uma fórmula aparecem dentro do escopo de algum quantificador dizemos que tal fórmula está completamente quantificada Abaixo temos um exemplo de fórmula completamente quantificada Considere agora a seguinte linguagem TQBF f f é uma fórmula Booleana completamente quantificada verdadeira O Teorema 89 de Sipser 2013 prova que TQBF Î PSPACEcompleta Logo também vale que TQBF Î PSPACE