Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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)

[img]
Preview
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-130.pdf - Other - Requires a PDF viewer.

Download (6Mb) | Preview

Request Changes to record.

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, Engineering and Medicine > 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:
DateEvent
July 1988Completion
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
Reuse Statement (publisher, data, author rights): M.S.&nbsp;Paterson and A.A.&nbsp;Razborov, &ldquo;The Set of Minimal Braids is co-NP-complete&rdquo;, <i>Journal of Algorithms</i> <b>12</b>, pp.&nbsp;393-408 (1991)
Funder: Science and Engineering Research Council (Great Britain) (SERC)
Related URLs:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us