Questions tagged [worst-case]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-3
votes
1answer
288 views

Are Graph and Group Isomorphism problems random self-reducible?

Are Graph and Group Isomorphism problems known to be random self-reducible? If so is there a good proof? Are there other non-trivial examples of random self-reducibility? Is there a good reference?
7
votes
2answers
405 views

What are the current best upper bounds of #P?

#P is the class of counting problems for problems in NP. In other words, a solution to #P returns the number of solutions to a particular problem in NP. I'm wondering if there have been any studies ...