To access the full text documents, please follow this link: http://hdl.handle.net/2117/8975

Generalized Hex and logical characterizations of polynomial space
Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
We extend a logical characterization of PSPACE due to Makowsky and Pnueli by showing that their logic has a particular normal form which implies that the Generalized Hex problem is complete for PSPACE via very restricted logical reductions. We also show that this normal form result fails in the absence of a built-in successor relation.
Peer Reviewed
Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi numèrica::Mètodes en elements finits
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
Computational complexity
Finite element method
Complexitat computacional
Elements finits, Mètode dels
info:eu-repo/semantics/publishedVersion
Article
         

Show full item record

Related documents

Other documents of the same author

Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Arratia Quesada, Argimiro Alejandro; Ortiz Gómez, Carlos
 

Coordination

 

Supporters