Improved lowness results for solvable black-box group problems (Q4370033)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1104166
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Improved lowness results for solvable black-box group problems |
scientific article; zbMATH DE number 1104166 |
Statements
29 November 1998
0 references
computational group theory
0 references
complexity
0 references
decision problems
0 references
solvable black-box groups
0 references
solvability tests
0 references
group isomorphisms
0 references
group factorizations
0 references
coset intersections
0 references
0.9293983
0 references
0.9210335
0 references
0.8987086
0 references
0.87944436
0 references
0.8761608
0 references
0.87616074
0 references
0.8518336
0 references
0.8326195
0 references
Improved lowness results for solvable black-box group problems (English)
0 references
Upper bounds on the complexity of the following decision problems over solvable black-box groups are computed: solvability testing, membership testing, order verification, group isomorphism, group intersection, group factorization, coset intersection, and double-coset membership. It is shown that these problems are either in SPP or in LWPP. (These results are in favor of the belief that these problems are unlikely to be complete for NP). For the entire collection see [Zbl 0879.00061].
0 references