In the context of $P$ vs $NP$, I was taught the following during my CS education:
- $P$ is the set of problems that can be solved in polynomial time
- $NP$ is the set of problems for which solutions can be verified in polynomial time
- Until $P$ vs $NP$ is solved, we only know that $P \subseteq NP$
However, I can also imagine a set of problems $X$, defined as the set of problems for which we can prove that a solution exists in polynomial time, without necessarily finding the solution itself. For example, assuming a problem instance that belongs to SAT:
- A solution to a SAT problem can be checked in polynomial time.
- A solution to a SAT problem be found in exponential time (if $P \neq NP$), or in polynomial time (if $P=NP$)
- However, the above does not answer how fast can we prove if a solution exists, without finding the solution itself.
Based on the above, I have the following question:
- What is the relation between $X$, $P$ and $NP$?
- Fundamentally, is finding a solution computationally equivalent to proving that a solution exists?
Personally, I find it reasonable that proving the existence of a solution should be fundamentally easier than constructing a specific solution. The former requires less information than the latter. However, this was rarely, if ever, discussed during my CS education.
EDIT: I corrected the definition of class X: "which we can prove that a solution exists in polynomial time, without necessarily finding the solution itself"