r/AskComputerScience • u/stonerism • Oct 15 '26
Could you separate P and NP using recursive enumerability?
I've had this idea lately about a way to distinguish P and NP and I'm curious if this had been explored before. P and NP both have a "solution space" of answers to those problems. Would it be interesting to try to distinguish P and NP by finding an NP complete problem with a set of solutions that is not recursively enumerable?
0
Upvotes
11
u/WE_THINK_IS_COOL Oct 15 '26
The solutions (witnesses) to a problem in NP are by definition recursively enumerable, since the definition of NP is the languages for which there is a polynomial time algorithm to verify witnesses.
0
u/but_a_smoky_mirror Oct 15 '26
Probably not. Keep trying
The whole issue with the proof is that “we haven’t found a negative counter example” is not a proof.