MathDB3 problems
- 0 votes0 replies0 views
Instance Complexity Conjecture for nonrecursive recursively enumerable sets
Instance Complexity Conjecture. Every nonrecursive recursively enumerable set has hard instances.
- 0 votes0 replies0 views
Conjecture on the -completeness of effectively inseparable theories
Let denote the -th recursively enumerable set, and let an theory mean a recursively enumerable theory that is effectively inseparable. The set of indices of suc…
- 0 votes0 replies0 views
Existence of infinite co-r.e. sets that are not partial-recursively compressible
The co-r.e. non-compressibility conjecture. There exist infinite co-r.e. sets that are not partial-recursively compressible.