Reiner Czerwinski

collaborators

4 papers

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.CC2023

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.CC2023

$L$ is unequal $N L$ under the Strong Exponential Time Hypothesis

Reiner Czerwinski

Due to Savitch's theorem we know $N L \subseteq D S P A C E (lo g^{2} (n))$ . To show this upper bound, Savitch constructed an algorithm with $O (lo g^{2} (n))$ space on the working tape. We will…

cs.CC2023

$P \neq = N P$ relative to a $P$ -complete oracle

Reiner Czerwinski

The $P$ versus $N P$ problem is still unsolved. But there are several oracles with $P$ unequal $N P$ relative to them. Here we will prove, that $P \neq = N P$ relative to a $P$ -complete…

The Polynomial Hierarchy does not collapse

NP-hard problems are not in BQP

L is unequal NL under the Strong Exponential Time Hypothesis

P=NP relative to a P-complete oracle

$L$ is unequal $N L$ under the Strong Exponential Time Hypothesis

$P \neq = N P$ relative to a $P$ -complete oracle