-1
$\begingroup$

I am going through a Turing machine topic. I know about decidable, semi decidable, and decidable problems. But honestly speaking, I did not get any practical examples of Semidecidable problems. Can you please share some examples or a URL link? Is the NP problem a semidecidable problem? If yes, then it means that NP-complete problems are Recursive enumerable. Please correct me if I am wrong.

I am thankful to you.

$\endgroup$

2 Answers 2

0
$\begingroup$

This is just equivalent to the class of RE problems (strictly RE\R). So one example would be finding whether a Diophantine equation has a solution.

  • A program could "solve" this problem by iterating through all possible combinations of variables, and testing them. If a solution exists, the program halts and returns yes. If a solution doesn't, the program does not halt.

Here is a wikipedia link for more information: https://en.wikipedia.org/wiki/RE_(complexity)

$\endgroup$
0
$\begingroup$

A problem in NP with the answer “yes” can be solved by getting a clever hint followed by a polynomial time verification.

We could solve it very very slowly by enumerating all possible hints.

Which means it is semidecidable, since solving the “yes” cases is enough to be semidecidable.

$\endgroup$

Your Answer

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

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