| Full text | |
| Author(s): |
de Araujo, Anderson
;
Finger, Marcelo
Total Authors: 2
|
| Document type: | Journal article |
| Source: | ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE; v. N/A, n. 81, p. 6-pg., 2012-01-01. |
| Abstract | |
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) | |
| FAPESP's process: | 10/51038-0 - Logical consequence, reasoning and computation - LOGCONS |
| Grantee: | Walter Alexandre Carnielli |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 08/03995-5 - Logprob: probabilistic logic --- foundations and computational applications |
| Grantee: | Marcelo Finger |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 11/07781-2 - Logical aspects of the quantum satisfiability problem |
| Grantee: | Anderson Beraldo de Araújo |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |