$P\not=NP$ relative to a $P$-complete oracle

Reiner Czerwinski

paper

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

arXiv:2305.02226

Abstract

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 oracle. In this paper, we use padding arguments as the proof method. The padding arguments are not bounded by a computable function. Such as we can use methods from computability theory to separate complexity classes.

P=NP relative to a P-complete oracle

Abstract

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