[Solved]: are there any decidable problems not verifiable in polynomial time?

Problem Detail: 

As I understand it NP requires a solution to be verifiable in polynomial time. Can you provide examples of solvable problems not verifiable in polynomial time ?

Asked By : user533933

Answered By : Raphael

Given input $x = \langle M \rangle$, decide whether $M$ halts after $|x|!$ steps on input $x$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28890

 Ask a Question

 Download Related Notes/Documents