3 papers
cs.CC2024
NP-hard problems are not in BQP
Reiner Czerwinski
Grover's algorithm can solve NP-complete problems on quantum computers faster than all the known algorithms on classical computers. However, Grover's algorithm still needs exponent…
cs.CC2024
The Polynomial Hierarchy does not collapse
Reiner Czerwinski
The arithmetical hierarchy (AH) is similar to the polynomial hierarchy (PH). Unlike the PH, the AH does not collapse relative to any oracle. A language in the (k + 1)-st level of t…
cs.CC2024
Separation of PSPACE and EXP
Reiner Czerwinski
This article shows that PSPACE not equal EXP. A simple but novel proof technique has been used to separate these two classes. Whether an arbitrary Turing machine accepts an input w…