0

It is well known that problems in the class P are characterized as those problems that are decidable in polynomial time by means of a deterministic Turing machine. My question is the following: If a decision problem can be decided by a deterministic procedure in polynomial time, i.e. it produces two possible outputs, YES or NOT, then the problem is in P? Is necessary to generate a computational procedure to solve the problem to guarantee that the problem is in P? Here it is clear that computability implies decidability however the inverse is not always true.

UnclePetros
  • 53
  • 1
    I don't quite get your question. What do you mean by "is it necessary to generate a computational procedure"? What do you mean by "computability" here? – tomasz Mar 27 '17 at 09:45
  • Decidability is usually defined in terms of computability: a decision problem is decidable if there is a computable function that correctly classifies all inputs as belonging or not belonging to some set. – mrp Mar 27 '17 at 09:56
  • For instance if I had a polynomial time method to decide whether the 3-SAT problem (, which is NP-complete) is true or not but I had not a method to generate an instance of values of literals that solve the problem, the problem 3-SAT could be considered as belonging to P? – UnclePetros Mar 27 '17 at 10:10
  • 1
    What is your definition of P? You describe something you call a "characterization" which as far as I can see is exactly the usual definition of P, and then ask whether problems that satisfy that characterization/definition are actually in P. What is the property beyond what you describe that you're uncertain whether they have? – hmakholm left over Monica Mar 27 '17 at 10:25
  • My main concern is on the definition of P, i.e. whether P is a class of problems of decision or not. For instance let us assume that I prove the decidability of the subset sum problem in polynomial time, i.e. I have a procedure that says YES there exists a subset satisfying the property of sum or NOT, but I do not provide any procedure to say a particular subset satisfying the property in case of the output of the decision problem is TRUE. Despite the fact that I have not computed this particular set, if my decision procedure is in polynomial time, the problem is considered in P? – UnclePetros Mar 27 '17 at 10:40

1 Answers1

0

Following your comment discussion, this might answer your question:

  1. The definition of $P$ (and NP as well) is concerned with decision problems only. So if you find a polynomial algorithm to solve 3-SAT that only gives "yes/no", and no actual solution, that is enough to prove that 3-SAT is in P.

  2. For all problems I can think of the distinction between the decision-problem and the computation-problem does not matter actually. Suppose you have a polynomial decision-algorithm for 3-SAT. In order to produce a solution you can simply run this algorithm multiple times on slightly smaller instances in wich you fix one single variable at a time. Depending on the answer of the decision-algorithm (which is only yes/no) you know the value of that single variable. Given that the decision-algorithm is polynomial, calling that algorihtm $n$ times is still polynomial.

Simon
  • 5,061