Let X be a problem for which pseudo-polynomial algorithm time for verification of solution exists. What can be said about complexity of problem X? Can X belong to NP-hard class?

  • 1
    $\begingroup$ Verifying the solution of the problem is known to be weakly NP-hard, i.e. pseudo-polynomial algorithm for verification exists. NP-hardness is a hardness property. Perhaps you wanted to say that the problem is in nondeterministic pseudopolynomial time? $\endgroup$ Commented Jan 30, 2020 at 14:30
  • $\begingroup$ As I understand this, for weak NP-hard problems, exact pseudo-polynomial time algorithm exists. Moreover, problem is in NP class if solution can be verified in polynomial time. For problem X, determining correctness of solution is weakly NP-hard, i.e. it is verified using pseudo-polynomial algorithm. This leads me to believe that problem X is certainly not in NP class? But can something other than that be concluded? $\endgroup$
    – dumpram
    Commented Jan 30, 2020 at 14:47
  • $\begingroup$ The halting problem is weakly NP-hard. $\endgroup$ Commented Jan 30, 2020 at 14:56
  • $\begingroup$ "The halting problem is weakly NP-hard." No. It is undecidable. $\endgroup$
    – dumpram
    Commented Jan 30, 2020 at 15:06
  • $\begingroup$ It's both weakly NP-hard and undecidable. $\endgroup$ Commented Jan 30, 2020 at 15:07


Your Answer

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