7 citations · 7 across the 8 of their papers we have counts for
8 papers
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 -complete language is comput…
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…
is unequal under the Strong Exponential Time Hypothesis
Reiner Czerwinski
Due to Savitch's theorem we know . To show this upper bound, Savitch constructed an algorithm with space on the working tape. We will…
relative to a -complete oracle
Reiner Czerwinski
The versus problem is still unsolved. But there are several oracles with unequal relative to them. Here we will prove, that relative to a -complete…
Incomplete sets in P for logspace-reduction
Reiner Czerwinski
In this article, we investigate the behaviour of TMs with time limit and tape space limit. This problem is in P when the time limit is unary coded. If both limits go to infinity, i…
Separation of P and NP
Reiner Czerwinski
There have been many attempts to solve the P versus NP problem. However, with a new proof method, P not equal NP can be proved. A time limit is set for an arbitrary Turing machine…
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…
A Polynomial Time Algorithm for Graph Isomorphism
Reiner Czerwinski
We claimed that there is a polynomial algorithm to test if two graphs are isomorphic. But the algorithm is wrong. It only tests if the adjacency matrices of two graphs have the sam…