NQP_C=co-C_=P

DOI10.1016/S0020-0190(99)00084-8zbMATH Open0999.68074OpenAlexW1555499558MaRDI QIDQ1606968FDOQ1606968

Authors: Tomoyuki Yamakami, Andrew Chi-Chih Yao 

Publication date: 25 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(99)00084-8

Recommendations

• \(\mathrm P \overset {?} {=} \mathrm{NP}\)
• QL(ℂⁿ) determines n
• \(\mathrm{QIP} = \mathrm{PSPACE}\)
• QIP = PSPACE
• (1, 1)-\(q\)-coherent pairs
• On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP
• scientific article; zbMATH DE number 3950504
• D.C. versus copositive bounds for standard QP
• scientific article; zbMATH DE number 6287555
• A non-unital \(^\ast\)-algebra has U\(C^\ast\)NP if and only if its unitization has U\(C^\ast\)NP

zbMATH Keywords

nondeterministic quantum polynomial-time complexity

Mathematics Subject Classification ID

Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (18)

• Polynomial time quantum computation with advice
• Approximate counting for complex-weighted Boolean constraint satisfaction problems
• A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
• More on quantum, stochastic, and pseudo stochastic languages with few states
• Quantum zero-error algorithms cannot be composed
• QUANTUM COMPUTATION WITH RESTRICTED AMPLITUDES
• Quantum alternation
• On interpolating between quantum and classical complexity classes
• Complexity bounds of constant-space quantum computation
• Quantum and classical complexity classes: Separations, collapses, and closure properties
• ANALYSIS OF QUANTUM FUNCTIONS
• \(\mathrm{QIP} = \mathrm{PSPACE}\)
• QIP = PSPACE
• Exact non-identity check is NQP-complete
• Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
• Theory of one-tape linear-time Turing machines
• A structured view on weighted counting with relations to counting, quantum computation and applications
• Quantum weakly nondeterministic communication complexity

This page was built for publication: \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1606968)