Complexity of n-Queens Completion
- Submitting institution
-
University of York
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 59972810
- Type
- D - Journal article
- DOI
-
10.1613/jair.5512
- Title of journal
- Journal of Artificial Intelligence Research (JAIR)
- Article number
- -
- First page
- 815
- Volume
- 59
- Issue
- -
- ISSN
- 1076-9757
- Open access status
- Compliant
- Month of publication
- August
- Year of publication
- 2017
- 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
-
2
- Research group(s)
-
-
- Citation count
- 12
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The n-Queens problem is used as a benchmark across many areas of artificial intelligence, despite its trivial complexity, leading to questions about the validity of experiments. We proved that a family of very similar problems are NP-hard and are therefore suitable benchmarks for AI algorithms. The paper attracted unexpected interest from the quantum computing community, and was covered in the press including the Scotsman, the National, and the Mail on Sunday website. An earlier version of the work was presented in the journal track of IJCAI 2018, the top AI conference.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -