b'\n_START_ARTICLE_\nF\xc3\xb3rmula booliana totalmente quantificada\n_START_SECTION_\nVis\xc3\xa3o geral\n_START_PARAGRAPH_\nNa teoria da complexidade computacional, o problema da quantifica\xc3\xa7\xc3\xa3o da f\xc3\xb3rmula booleana(QBF)\xc3\xa9 uma generaliza\xc3\xa7\xc3\xa3o do problema de satisfatibilidade booleana em que ambos, quantificadores existenciais e quantificadores universais podem ser aplicados a cada vari\xc3\xa1vel. Dito de outra forma, pergunta se uma forma sentencial quantificada sobre um conjunto de vari\xc3\xa1veis booleanas \xc3\xa9 verdadeira ou falsa. Por exemplo, a inst\xc3\xa2ncia seguinte \xc3\xa9 um exemplo de QBF:_NEWLINE_\xe2\x88\x80x \xe2\x88\x83y \xe2\x88\x83z (( x \xe2\x88\xa8 z ) \xe2\x88\xa7 y)_NEWLINE_QBF \xc3\xa9 o problema can\xc3\xb4nico completo para PSPACE, a classe de problemas sol\xc3\xbaveis por uma M\xc3\xa1quina de Turing deternin\xc3\xadstica ou n\xc3\xa3o determin\xc3\xadstica no espa\xc3\xa7o polinomial e tempo ilimitado[1]. Dada uma f\xc3\xb3rmula na \xc3\xa1rvore de sintaxe abstrata, o problema pode ser resolvido por um conjunto de procedimentos mutuamente recursivo que avalia a f\xc3\xb3rmula. Tal algoritmo usa o espa\xc3\xa7o proporcional \xc3\xa0 altura da \xc3\xa1rvore, o qual \xc3\xa9 linear no pior caso, mas usa o tempo exponencial no n\xc3\xbamero de quantificadores._NEWLINE_Desde que MA \xe2\x8a\x82 PSPACE, o que se acredita amplamente, QBF n\xc3\xa3o pode ser resolvido, nem mesmo uma solu\xc3\xa7\xc3\xa3o dada pode ser verificada em qualquer tempo determin\xc3\xadstico e probabil\xc3\xadstico polinomial(de fato, ao contr\xc3\xa1rio do problema da satisfatibilidade, n\xc3\xa3o h\xc3\xa1 qualquer maneira conhecida para especificar uma solu\xc3\xa7\xc3\xa3o de forma sucinta). \xc3\x89 trivial resolver usando uma M\xc3\xa1quina de Turing Alternada em tempo linear que n\xc3\xa3o \xc3\xa9 nenhuma surpresa uma vez que, de fato, AP = PSPACE, onde AP \xc3\xa9 a classe de problemas que podem ser resolvidas por m\xc3\xa1quinas alternadas em tempo polinomial[2]._NEWLINE_Quando o resultado seminal IP = PSPACE foi mostrado(veja sistema de prova interativa), foi feito para exibir um sistema de prova interativa que poderia resolver QBF resolvendo uma aritmetiza\xc3\xa7\xc3\xa3o particular do problema [3]._NEWLINE_As f\xc3\xb3rmulas em QBF tem uma s\xc3\xa9rie de formas can\xc3\xb4nicas \xc3\xbateis. Por exemplo, pode-se mostrar que h\xc3\xa1 uma redu\xc3\xa7\xc3\xa3o muitos-para-um em tempo polinomial que ir\xc3\xa1 mover todos os quantificadores para frente da f\xc3\xb3rmula e ent\xc3\xa3o altern\xc3\xa1-los entre quantificadores universal e existencial. H\xc3\xa1 outra redu\xc3\xa7\xc3\xa3o que prova ser \xc3\xbatil no IP = PSPACE, onde n\xc3\xa3o mais que um quantificador universal \xc3\xa9 colocado entre o o uso de cada vari\xc3\xa1vel e a liga\xc3\xa7\xc3\xa3o entre o quantificador e a vari\xc3\xa1vel. Isso foi fundamental no limite do n\xc3\xbamero de produtos em certas subexpress\xc3\xb5es da aritmetiza\xc3\xa7\xc3\xa3o.\n_START_SECTION_\nForma normal prenex\n_START_PARAGRAPH_\nUma f\xc3\xb3rmula booleana totalmente quantificada pode ser considerada para ter uma forma muito espec\xc3\xadfica, chamada forma normal prenex. Ela tem duas partes b\xc3\xa1sicas: uma por\xc3\xa7\xc3\xa3o contendo quantificadores e s\xc3\xb3 uma parte contendo uma f\xc3\xb3rmula booleana n\xc3\xa3o quantificada, normalmente denotada como \xcf\x86. Se existem n vari\xc3\xa1veis booleanas, toda a f\xc3\xb3rmula pode ser escrita como:_NEWLINE_\xe2\x88\x83x\xe2\x82\x81\xe2\x88\x80x\xe2\x82\x82\xe2\x88\x83x\xe2\x82\x81...Q\xe2\x82\x99x\xe2\x82\x99\xce\xa6(x\xe2\x82\x81, x\xe2\x82\x82, x\xe2\x82\x83 ... x\xe2\x82\x99)_NEWLINE__NEWLINE_onde cada vari\xc3\xa1vel se insere no \xc3\xa2mbito de algum quantificador. Com a introdu\xc3\xa7\xc3\xa3o de vari\xc3\xa1veis fict\xc3\xadcias qualquer f\xc3\xb3rmula na forma normal prenex pode ser convertida em uma senten\xc3\xa7a onde quantificadores existencial e universal alternados. Usando a vari\xc3\xa1vel fict\xc3\xadcia "y1",_NEWLINE_\xe2\x88\x83x\xe2\x82\x81\xe2\x88\x83x\xe2\x82\x82\xce\xa6(x\xe2\x82\x81, x\xe2\x82\x82) \xe2\x87\x94 \xe2\x88\x83x\xe2\x82\x81\xe2\x88\x80y\xe2\x82\x81\xe2\x88\x83x\xe2\x82\x82\xce\xa6(x\xe2\x82\x81, x\xe2\x82\x82)_NEWLINE__NEWLINE_A segunda senten\xc3\xa7a teve o mesmo valor verdade, mas segue a sintaxe restrita. Assumindo que a convers\xc3\xa3o de f\xc3\xb3rmulas booleanas totalmente quantificadas para a forma normal prenex \xc3\xa9 uma caracter\xc3\xadstica frequente de provas.\n_START_SECTION_\nResolvendo\n_START_PARAGRAPH_\nH\xc3\xa1 um simples algoritmo para verificar se um TBQF \xc3\xa9 verdade. Dadas algumas QBF:_NEWLINE_Q\xe2\x82\x81x\xe2\x82\x81Q\xe2\x82\x82x\xe2\x82\x82...Q\xe2\x82\x99x\xe2\x82\x99\xce\xa6(x\xe2\x82\x81, x\xe2\x82\x82, ..., x\xe2\x82\x99)_NEWLINE_Se a f\xc3\xb3rmula n\xc3\xa3o cont\xc3\xa9m quantificadores, podemos simplesmente voltar a f\xc3\xb3rmula. Caso contr\xc3\xa1rio, tiramos o primeiro quantificador e verificamos os valores poss\xc3\xadveis para a primeira vari\xc3\xa1vel:_NEWLINE_A = Q\xe2\x82\x82x\xe2\x82\x82 ... Q\xe2\x82\x99x\xe2\x82\x99\xce\xa6(0, x\xe2\x82\x82, ..., x\xe2\x82\x99),_NEWLINE_B = Q\xe2\x82\x82x\xe2\x82\x82 ... Q\xe2\x82\x99x\xe2\x82\x99\xce\xa6(1, x\xe2\x82\x82, ..., x\xe2\x82\x99)._NEWLINE_Se Q\xe2\x82\x81 = \xe2\x88\x83, ent\xc3\xa3o retorne A \xe2\x88\xa8 B. Se Q\xe2\x82\x81 = \xe2\x88\x80, ent\xc3\xa3o retorne A \xe2\x88\xa7 B. Qu\xc3\xa3o r\xc3\xa1pido executa esse algoritmo? Para cada quantificador na QBF inicial, o algoritmo faz duas chamadas recursivas em apenas um problema linearmente menor. Isso d\xc3\xa1 ao algoritmo um tempo de execu\xc3\xa7\xc3\xa3o exponencial O (2 ^ n)._NEWLINE_Quanto de espa\xc3\xa7o esse algoritmo usa? Em cada chamada do algoritmo \xc3\xa9 necess\xc3\xa1rio armazenar os resultados intermedi\xc3\xa1rios da computa\xc3\xa7\xc3\xa3o de A e B. Cada chamada recursiva tira um quantificador, apenas a profundidade recursiva \xc3\xa9 linear no n\xc3\xbamero de quantificadores. F\xc3\xb3rmulas que faltam quantificadores podem ser avaliados no espa\xc3\xa7o logaritmico no n\xc3\xbamero de vari\xc3\xa1veis. O QBF inicial foi totalmente quantificado, por isso h\xc3\xa1 tanto quantificadores quanto vari\xc3\xa1veis. Assim, o algoritmo usa de espa\xc3\xa7o O ( n + log n ) = O ( n). Isso faz TQBF parte da classe de complexidade PSPACE.\n_START_SECTION_\nPSPACE completude\n_START_PARAGRAPH_\nA linguagem TQBF serve na teoria da complexidade como a can\xc3\xb4nica do problema PSPACE-completo. Sendo PSPACE-completo significa que uma linguagem est\xc3\xa1 em PSPACE e que a linguagem tamb\xc3\xa9m \xc3\xa9 PSPACE-dif\xc3\xadcil. O algoritmo acima mostra que TBQF est\xc3\xa1 em PSPACE. Mostrar que uma linguagem est\xc3\xa1 em PSPACE-dif\xc3\xadcil, requer mostrar que qualquer linguagem na classe de complexidade PSPACE pode ser reduzida, em tempo polinomial, a TQBF. Ou seja,_NEWLINE_\xe2\x88\x80L \xe2\x88\x88 PSPACE, L \xe2\x89\xa4\xe2\x82\x9a TQBF._NEWLINE_Isso significa que para uma linguagem L SPACE, se uma linguagem x est\xc3\xa1 em L pode ser decidida por verificar se f(x) est\xc3\xa1 na TQBF, para alguma fun\xc3\xa7\xc3\xa3o f que \xc3\xa9 necess\xc3\xa1ria para executar em tempo polinomial (em rela\xc3\xa7\xc3\xa3o ao comprimento da entrada). Simbolicamente:_NEWLINE_x \xe2\x88\x88 L \xe2\x87\x94 f(x) \xe2\x88\x88 TQBF._NEWLINE_Provar que TBQF est\xc3\xa1 em PSPACE-dif\xc3\xadcil requer uma especifica\xc3\xa7\xc3\xa3o de f. Ent\xc3\xa3o, suponhamos que L \xc3\xa9 uma linguagem PSPACE. Isso significa que L pode ser decidida por uma m\xc3\xa1quina de Turing determin\xc3\xadstica no espa\xc3\xa7o polinomial(MTD). Isso \xc3\xa9 muito importante para a redu\xc3\xa7\xc3\xa3o de L a TQBF, porque as configura\xc3\xa7\xc3\xb5es de qualquer m\xc3\xa1quina de turing pode ser representada como f\xc3\xb3rmulas booleanas, com vari\xc3\xa1veis booleanas que representam o estado da m\xc3\xa1quina, bem como o conte\xc3\xbado da fita em cada c\xc3\xa9lula da m\xc3\xa1quina de Turing. Com a posi\xc3\xa7\xc3\xa3o da cabe\xc3\xa7a da m\xc3\xa1quina de Turing codificada na f\xc3\xb3rmula por ordena\xc3\xa7\xc3\xb5es da f\xc3\xb3rmula. Em particular, nossa redu\xc3\xa7\xc3\xa3o vai usar as vari\xc3\xa1veis C\xe2\x82\x81 e C\xe2\x82\x82, que representam duas configura\xc3\xa7\xc3\xb5es poss\xc3\xadveis da MTD para L, e t um n\xc3\xbamero natural, na constru\xc3\xa7\xc3\xa3o de uma QBF \xce\xa6c1, c2, t, o qual \xc3\xa9 verdadeiro, se e somente se a MTD para L pode ir de uma configura\xc3\xa7\xc3\xa3o codificada em c\xe2\x82\x81 em n\xc3\xa3o mais que t passos. Ent\xc3\xa3o, a fun\xc3\xa7\xc3\xa3o f construir\xc3\xa1 da MTD para L uma QBF \xce\xa6 c\xe2\x82\x9b\xe2\x82\x9c\xe2\x82\x90\xe1\xb5\xa3\xe2\x82\x9c, caccept, T , onde c\xe2\x82\x9b\xe2\x82\x9c\xe2\x82\x90\xe1\xb5\xa3\xe2\x82\x9c \xc3\xa9 uma configura\xc3\xa7\xc3\xa3o inicial da MTD, caccept \xc3\xa9 a configura\xc3\xa7\xc3\xa3o de aceita\xc3\xa7\xc3\xa3o da MTD e T \xc3\xa9 o n\xc3\xbamero m\xc3\xa1ximo de passos que uma MTD poderia precisar para mudar de uma configura\xc3\xa7\xc3\xa3o para outra. Sabemos que T = O (exp ( n )), onde n \xc3\xa9 o tamanho da entrada porque esta limita o n\xc3\xbamero de configura\xc3\xa7\xc3\xb5es poss\xc3\xadveis de relev\xc3\xa2ncia na MTD. \xc3\x89 claro que a MTD n\xc3\xa3o pode tomar as medidas mais que as configura\xc3\xa7\xc3\xb5es possiveis para chegar a caceita, a menos que ela entre em loop. De qualquer forma, ela nunca vai chegar a caceita._NEWLINE_Nessa fase da prova, n\xc3\xb3s j\xc3\xa1 reduzimos a quest\xc3\xa3o de saber se uma f\xc3\xb3rmula de entrada w (codificado, \xc3\xa9 claro, em c\xe2\x82\x9b\xe2\x82\x9c\xe2\x82\x90\xe1\xb5\xa3\xe2\x82\x9c) est\xc3\xa1 em L para a quest\xc3\xa3o de saber se o QBF \xce\xa6C\xe2\x82\x9b\xe2\x82\x9c\xe2\x82\x90\xe1\xb5\xa3\xe2\x82\x9c, Caccept, T,, ou seja, f( w ) est\xc3\xa1 em TQBF. O restante dessa prova mostra que f pode ser computada em tempo polinomial._NEWLINE_Para t = 1, c\xc3\xa1lculo de \xce\xa6c1,c2,t \xc3\xa9 simples - ou uma configura\xc3\xa7\xc3\xb5es muda para outro passo ou n\xc3\xa3o. A m\xc3\xa1quina de Turing que representa a nossa f\xc3\xb3rmula \xc3\xa9 determin\xc3\xadstica, esta n\xc3\xa3o apresenta nenhum problema. Para t > 1, o c\xc3\xa1lculo de \xce\xa6c1,c2,t envolve uma avalia\xc3\xa7\xc3\xa3o recursiva, \xc3\xa0 procura de um assim chamado \xe2\x80\x9cponto m\xc3\xa9dio\xe2\x80\x9d m\xe2\x82\x81. Neste caso, reescrevemos a f\xc3\xb3rmula seguinte:_NEWLINE_\xce\xa6c1,c2,t = \xe2\x88\x83m\xe2\x82\x81(\xce\xa6c1,m1,[t/2] \xe2\x88\xa7 \xce\xa6m1,c2,[t/2])._NEWLINE_Esta f\xc3\xb3rmula converte a quest\xc3\xa3o de saber se um c um pode chegar a c\xe2\x82\x82 em t etapas, para a quest\xc3\xa3o de saber se c\xe2\x82\x81 atinge um ponto m\xc3\xa9dio m\xe2\x82\x81 em t/2 etapas, que se alcan\xc3\xa7a c\xe2\x82\x82 em t / 2 passos. A resposta a \xc3\xbaltima pergunta, naturalmente, d\xc3\xa1 resposta \xc3\xa0 primeira._NEWLINE_Agora, t \xc3\xa9 apenas limitado por T, que \xc3\xa9 exponencial(e por isso, n\xc3\xa3o polnomial) no comprimento da entrada. Al\xc3\xa9m disso, cada camada recursiva, praticamente, dobra o tamanho da f\xc3\xb3rmula. (A vari\xc3\xa1vel m 1 \xc3\xa9 apenas um ponto m\xc3\xa9dio - para t maior existem mais paradas ao longo do caminho, por assim dizer). Assim, o tempo necess\xc3\xa1rio para avaliar recursivamente (f\xc3\xb3rmula) desta forma poderia ser exponencial, bem como, simplesmente porque a f\xc3\xb3rmula poderia se tornar exponencialmente grande. Este problema \xc3\xa9 resolvido com o uso de um quantificador universal, usando as vari\xc3\xa1veis c 3 e c 4 sobre os pares de configura\xc3\xa7\xc3\xb5es, (por exemplo, {( c\xe2\x82\x81 , m\xe2\x82\x81 ), ( m\xe2\x82\x81 , c\xe2\x82\x82 )}), que impede a extens\xc3\xa3o da f\xc3\xb3rmula devida para expans\xc3\xa3o das camadas recursivas. Isso gera a seguinte interpreta\xc3\xa7\xc3\xa3o \xce\xa6c1,c2,t:_NEWLINE_\xce\xa6c1,c2,t = \xe2\x88\x83 m\xe2\x82\x81 \xe2\x88\x80 (c\xe2\x82\x83, c\xe2\x82\x83) \xe2\x88\x88 {(c\xe2\x82\x81, m\xe2\x82\x81), (m\xe2\x82\x81, c\xe2\x82\x82)}(\xce\xa6c3,c4,[t/2])._NEWLINE_Esta vers\xc3\xa3o da f\xc3\xb3rmula pode, realmente, ser computada em tempo polinomial. O par ordenado universalmente quantificado simplesmente nos diz que qualquer escolha de ( c\xe2\x82\x83 , c\xe2\x82\x84 ) \xc3\xa9 feita, \xce\xa6c1,c2,t \xe2\x87\x94 \xce\xa6c3,c4,[t/2]._NEWLINE_Assim, \xe2\x88\x80L \xe2\x88\x88 PSPACE, L \xe2\x89\xa4\xe2\x82\x9a TQBF por isso, TQBF est\xc3\xa1 em PSPACE-dif\xc3\xadcil. Juntamente com o resultado acima de que TQBF est\xc3\xa1 em PSPACE, isso completa a prova de que TQBF est\xc3\xa1 em PSPACE-completo._NEWLINE_(Esta prova segue Sipser pp. 310-313 2006 em todos os fundamentos. Papadimitriou 1994 tamb\xc3\xa9m inclui uma prova).'