Dissertação

{en_GB=Computational Complexity of Games and Puzzles } {} EVALUATED

{pt=Nesta tese, estudamos várias técnicas e resultados da relação entre a Teoria da Complexidade e Jogos. Usamos as técnicas estudadas para obter novos resultados. As nossas contribuições para com os jogos Hexiom, Cut the Rope e Back to Bed poderão ser úteis para obter futuros resultados noutros jogos, porque tiram partido de estrutura comum a vários jogos que ainda não foram estudados. Também salientamos possíveis direcções para estudo adicional, especialmente em relação à incerteza, algo prevalente nos jogos modernos mas ainda pouco estudado. , en=In this thesis, we survey techniques and results from the study of Complexity Theory and Games. We then apply these techniques to obtain new results for previously unstudied games. Our contributions in the games Hexiom, Cut the Rope, and Back to Bed may be helpful in further studies by exploiting structure common to several games. We also highlight some interesting paths for further study, related to uncertainty, that have yet to receive thorough study given their prevalence in today's games.}
{pt=jogos, puzzles, complexidade, reduções, en=games, puzzles, complexity, reductions}

Julho 18, 2018, 9:0

Orientação

ORIENTADOR

Luís Manuel Silveira Russo

Departamento de Engenharia Informática (DEI)

Professor Auxiliar

ORIENTADOR

Alexandre Paulo Lourenço Francisco

Departamento de Engenharia Informática (DEI)

Professor Auxiliar