The Library
The set of minimal braids is co-NP-complete
Tools
Tools
Tools
Paterson, Michael S. and Razborov, Alexander (1988) The set of minimal braids is co-NP-complete. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-130.pdf - Other - Requires a PDF viewer. Download (6Mb) | Preview |
Abstract
Braids can be represented as two-dimensional diagrams showing the crossings of strings or as words over the generators of a braid group. A minimal braid is one with the fewest crossings (or the shortest words) among all possible representations topologically equivalent to that braid. The main result of this paper is that the set of minimal braids is co-NP-complete.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Braid theory | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | July 1988 | ||||
| Dates: |
|
||||
| Number: | Number 130 | ||||
| Number of Pages: | 16 | ||||
| DOI: | CS-RR-130 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Publisher Statement: | M.S. Paterson and A.A. Razborov, “The Set of Minimal Braids is co-NP-complete”, <i>Journal of Algorithms</i> <b>12</b>, pp. 393-408 (1991) | ||||
| Funder: | Science and Engineering Research Council (Great Britain) (SERC) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
