Reiner Czerwinski

activity

20072024

most citedA Polynomial Time Algorithm for Graph Isomorphism

7 citations · 7 across the 8 of their papers we have counts for

collaborators

Showing 2023Show all

3 papers · 1 filter

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…

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