Some Quantitative Aspects of Fractional Computability
| dc.creator | Kapovich, Ilya | |
| dc.creator | Schupp, Paul | |
| dc.date | 2007-06-27 | |
| dc.date.accessioned | 2026-07-07T08:12:58Z | |
| dc.date.available | 2026-07-07T08:12:58Z | |
| dc.description | Motivated by results on generic-case complexity in group theory, we apply the ideas of effective Baire category and effective measure theory to study complexity classes of functions which are "fractionally computable" by a partial algorithm. For this purpose it is crucial to specify an allowable effective density, $δ$, of convergence for a partial algorithm. The set $\mathcal{FC}(δ)$ consists of all total functions $ f: Σ^\ast \to \{0,1 \}$ where $Σ$ is a finite alphabet with $|Σ| \ge 2$ which are "fractionally computable at density $δ$". The space $\mathcal{FC}(δ) $ is effectively of the second category while any fractional complexity class, defined using $δ$ and any computable bound $β$ with respect to an abstract Blum complexity measure, is effectively meager. A remarkable result of Kautz and Miltersen shows that relative to an algorithmically random oracle $A$, the relativized class $\mathcal{NP}^A$ does not have effective polynomial measure zero in $\mathcal{E}^A$, the relativization of strict exponential time. We define the class $\mathcal{UFP}^A$ of all languages which are fractionally decidable in polynomial time at ``a uniform rate'' by algorithms with an oracle for $A$. We show that this class does have effective polynomial measure zero in $\mathcal{E}^A$ for every oracle $A$. Thus relaxing the requirement of polynomial time decidability to hold only for a fraction of possible inputs does not compensate for the power of nondeterminism in the case of random oracles. | |
| dc.identifier | https://arxiv.org/abs/0706.4095 | |
| dc.identifier | http://arxiv.org/abs/0706.4095 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/132644 | |
| dc.subject | Group Theory | |
| dc.subject | Computational Complexity | |
| dc.subject | Primary 68Q, Secondary 20P05 | |
| dc.title | Some Quantitative Aspects of Fractional Computability | |
| dc.type | text |