The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
1answer
61 views

What does it mean for something to be $\prod_x^y$-complete or $\sum_x^y$-complete?

I'm having trouble understanding the definitions for complexity classes in the arithmetic heirarchy, and because of the naming schemes, "Googling" things is somewhat difficult. Can anyone provide me ...
2
votes
3answers
43 views

Recursive methods with stacks

I'm doing some practice papers for revision for my finals and I came across this question: "This question is about recursion. A recursive method can always be implemented by an iterative method ...
6
votes
0answers
54 views

Is There a Complete Problem for the Class of Turing Decidable Problems?

Languages such as $\text{HALT}_{TM}$ are $\textsf{RE-complete}$ under many-one reductions. It is trivial to see that $\text{co-RE}$ has complete problems, too. S. Schmitz [1] considers some classes ...