All Questions
4 questions
18
votes
2
answers
1k
views
Is there a name for sets for which it is easier to test membership than to find members---and vice versa?
This is a question my son Bob asked me. For some sets it is relatively easy
to test for membership but a lot more difficult to find members, and for others
the reverse is true. Here is an elementary ...
- 15.3k
17
votes
1
answer
960
views
Polynomial-time algorithm to compare numbers in Conway chained arrow notation
I am looking for a polynomial-time algorithm which, given a character string containing two numbers in Conway's chained arrow notation for large numbers, indicates whether the first number is less ...
- 171
6
votes
2
answers
276
views
Extending polynomial hierarchy above $\omega$
The arithmetic hierarchy is naturally extended to all ordinals via ordinal notations creating a hierarchy for all hyperarithmetic sets. The polynomial time hierarchy is defined analogously to the ...
- 3,029
1
vote
0
answers
127
views
Does relationship between c.e.set, productive set, immune set, ML-random set exist between sets of class of other level
Is relationship between c.e.set, productive set, immune set, ML-random set similar to relationship between polynomial complexity set, polynomial complexity-productive set, P-immune set, P-random set?
- 3,094