Unique End of Potential Line
- Submitting institution
-
The University of Liverpool
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 15774
- Type
- D - Journal article
- DOI
-
10.1016/j.jcss.2020.05.007
- Title of journal
- Journal of Computer and System Sciences
- Article number
- -
- First page
- 1
- Volume
- 114
- Issue
- -
- ISSN
- 0022-0000
- Open access status
- Compliant
- Month of publication
- June
- Year of publication
- 2020
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
3
- Research group(s)
-
-
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- A preliminary version of this paper appeared at ICALP'19, following a preprint titled "End of Potential Line". The paper resolves an open question (Problem 6) of Gil Kalai from his plenary lecture "Three puzzles on mathematics, computation, and games" at the 2018 International Congress of Mathematicians, by showing that the Unique Sink Orientation problem is in the new complexity class, UEOPL, defined in the paper. The importance of UEOPL has been further highlighted by follow-up work in the area: For example, the main result of "Computational Complexity of the alpha-Ham-Sandwich Problem" (ICALP'20) is the containment of a problem in UEOPL.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -