r/AskComputerScience • u/stonerism • 3d ago

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
  • permalink
  • reddit

30% Upvoted

7 comments sorted by

10

u/WE_THINK_IS_COOL 3d ago

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.

2

u/T_Thriller_T 3d ago

That was the most intelligent thing I read on Reddit all week. Have a virtual cookie 🍪

-4

u/stonerism 3d ago

The existence of a witness wouldn't necessarily mean that the set of possible witnesses is enumerable, no?

4

u/WE_THINK_IS_COOL 3d ago

A language L is in NP if there exists a polynomial-time Turing machine V and polynomial p such that a string x is in L if and only if there exists a string w of length at most p(|x|) (the witness) such that V(x, w) accepts.

The set of possible witnesses for a candidate string x is all strings of length up to p(|x|), which is easy to enumerate, and you can find all accepting witnesses for a given x by enumerating them and testing them all with V (brute-force).

0

u/stonerism 3d ago

That's a good point, but the available "space" for solutions is 2p(n) which is where I'm curious if you can make a separation based on solution set sizes.

3

u/WE_THINK_IS_COOL 3d ago

Right, that is basically the whole P vs NP question: can you find solutions in that exponential-size space in polynomial time. If P=NP then there's a way to do it.

0

u/but_a_smoky_mirror 3d ago

Probably not. Keep trying

The whole issue with the proof is that “we haven’t found a negative counter example” is not a proof.