Unambiguous computation boolean hierarchies and sparse turing-complete sets.
It is known that for any class C closed under union and intersection, the Boolean closure of C, the Boolean hierarchy over C and the symmetric difference hierarchy over C all are equal. We prove that these equalities hold for any complexity class closed under intersection; in particular, they thus h...
| প্রকাশিত: | SIAM journal on computing. 26, 3 (1997). |
|---|---|
| প্রধান লেখক: | |
| বিন্যাস: | প্রবন্ধ |
| ভাষা: | English |
| বিষয়গুলি: |