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
