| Texto completo | |
| Autor(es): |
de Araujo, Anderson
;
Finger, Marcelo
Número total de Autores: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE; v. N/A, n. 81, p. 6-pg., 2012-01-01. |
| Resumo | |
We present the linear algebraic definition of QSAT and propose a direct logical characterization of such a definition. We then prove that this logical version of QSAT is not an extension of classical satisfiability problem (SAT). This shows that QSAT does not allow a direct comparison between the complexity classes NP and QMA, for which SAT and QSAT are respectively complete. (AU) | |
| Processo FAPESP: | 10/51038-0 - Logical consequence, reasoning and computation - LOGCONS |
| Beneficiário: | Walter Alexandre Carnielli |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 08/03995-5 - LOGPROB: lógica probabilística - fundamentos e aplicações computacionais |
| Beneficiário: | Marcelo Finger |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 11/07781-2 - Aspectos lógicos do problema da satisfatibilidade quântica |
| Beneficiário: | Anderson Beraldo de Araújo |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |