Search code examples
complexity-theorytheorynumber-theory

Time and Space Complexity for PCP and Halting Problem


So PCP is semi-decidable and undecidable and Halting Problem is undecidable. Is it even possible to name a time complexity for them, like NP or expTime?

And what about space Complexity: are they in Pspace?


Solution

  • So as @walnut stated they are in neither of the mentioned complexity classes because the classes requires there to be an algorithm that decides the problem in the first place.Thank you for your answer :)