0
$\begingroup$

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"

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

$\mathsf{P}$ and $\mathsf{NP}$ are classes of decision problems. It means that for an instance of such a problem, the question is always a Yes-No question.

Since you define $X$ as "the set of problems for which we can prove that a solution exists in polynomial time", there is a bit of ambiguity: are those problems decision problems? Optimisation problems? Search problems?

However, since the question you are asking is whether or not there exists a solution, there is a clear correspondance between $X$ and $\mathsf{P}$: given a problem $A\in X$ and $x$ an instance of $A$, what your polynomial algorithm do is solve the decision problem:

Instance: $x$ an instance of $A$.

Question: does there exist a solution to $A$ with instance $x$?

Improve this answer
$\endgroup$
5
  • $\begingroup$ Right, I am always considering decision problems. However, I think i had the wrong idea that for P and NP solutions have to be constructive. (1) In the phrase " P contains all decision problems that can be SOLVED in polynomial time", what is the exact meaning of SOLVED? Does it have to be constructive solution or can it also be non-constructive? (2) Would the discovery of a polynomial and non-constructive algorithm for deciding SAT problems also prove P=NP, even though we would have no idea how to construct a solution in polynomial time? $\endgroup$
    – Enk9456
    Dec 9, 2022 at 19:36
  • 1
    $\begingroup$ "Solved in polynomial time" means that you can find in polynomial time if the answer to the question is "Yes" or "No". What would a "constructive" solution to a Yes-No question be? I am not sure I understand what you mean here. $\endgroup$
    – Nathaniel
    Dec 9, 2022 at 19:44
  • $\begingroup$ As an example, consider the question "Is $n$ a prime integer?". For $n$ an integer, the answer is either Yes or No. What is a constructive solution to this problem? $\endgroup$
    – Nathaniel
    Dec 9, 2022 at 19:49
  • $\begingroup$ An instance of SAT is a decision problem with a Yes/No answer. By constructive, I mean to answer "Yes" by finding a specific assignment of boolean variables that makes the expression TRUE. By non-constructive, I mean to somehow find out that there must exist such an assignment of variables, without finding it explicitly. -- I agree however that this distinction makes no sense for the prime integer question $\endgroup$
    – Enk9456
    Dec 9, 2022 at 20:06
  • 1
    $\begingroup$ If you want to find a specific assignment, you are not considering a decision problem, and thus not the problem SAT. If you want to know whether there exists a satisfying assignment, you are considering exactly the SAT problem. $\endgroup$
    – Nathaniel
    Dec 9, 2022 at 20:51
0
$\begingroup$

You are pretty much asking if there is a broader set of algorithms $X$ such that for some decision problem $p$, there is a non-constructive proof that $p\in P$.

This set would be separate from the classes $P, NP$ as those sets only care about the existence of solutions, whether or not they are actually constructable is not needed.

Its also pretty easy to show that $X\subset P$, as any member of $X$ is in $P$ by definition, but we know of problems in $P$ that have constructed solutions.

As for if there is a name for this set of problems, not that I am aware of, but research is pretty expansive to maybe in a paper I'm not familiar with

Improve this answer
$\endgroup$
4
  • $\begingroup$ I corrected the definition of class X: "which we can prove that a solution exists in polynomial time, without necessarily finding the solution itself" $\endgroup$
    – Enk9456
    Dec 9, 2022 at 19:40
  • $\begingroup$ Yes, that is what I mean by a "non-constructive proof" in which we can say "we know that a polynomial time decision algorithm exists, but we just don't know what it is". For a decision problem to be in $P$ an algorithm just needs to exist, not actually be described $\endgroup$
    – wjmccann
    Dec 9, 2022 at 19:43
  • $\begingroup$ Or do you mean, prove that a solution exists for a given input without actually determining the answer. So like for traveling salesman it will just say "yes this input has a solution" in polynomial time without giving a path? $\endgroup$
    – wjmccann
    Dec 9, 2022 at 19:45
  • $\begingroup$ I mean the second one, as in the traveling salesman example. $\endgroup$
    – Enk9456
    Dec 9, 2022 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.