1
$\begingroup$

As stated, is there any decision problems in the complexity class RE that are neither RE-complete nor recursive?

It seems that almost all of nonrecursive RE problems are in RE-complete...

1 Answers 1

3

This is known as Post's problem and the answer is yes. The first such problem (and the only one I am familiar with) was constructed using forcing and the method of finite injury.