Soccer is Harder Than Football

Jan Christensen; Anders Nicolai Knudsen; Kim Skak Larsen

doi:10.1142/S0129054115500264

Soccer is Harder Than Football

Jan Christensen, Anders Nicolai Knudsen, Kim Skak Larsen

Department of Mathematics and Computer Science

University of Southern Denmark

Research output: Contribution to journal › Journal article › Research › peer-review

Abstract

It is known that deciding whether or not a team in a soccer tournament in progress can still win or, more generally, can obtain a certain position is NP-complete. We show that deciding whether or not a team is guaranteed a certain minimum position is coNP-complete. We also show that deciding with regards to goal difference, the standard tie-breaker for teams having the same number of points, whether or not a team can reach a certain position is NP-complete.

Original language	English
Journal	International Journal of Foundations of Computer Science
Volume	26
Issue number	4
Pages (from-to)	477-486
ISSN	0129-0541
DOIs	https://doi.org/10.1142/S0129054115500264
Publication status	Published - 2015

Documents & Links

10.1142/S0129054115500264

Cite this

@article{1fff0168c6254b26a83a62fd13790490,

title = "Soccer is Harder Than Football",

abstract = "It is known that deciding whether or not a team in a soccer tournament in progress can still win or, more generally, can obtain a certain position is NP-complete. We show that deciding whether or not a team is guaranteed a certain minimum position is coNP-complete. We also show that deciding with regards to goal difference, the standard tie-breaker for teams having the same number of points, whether or not a team can reach a certain position is NP-complete.",

author = "Jan Christensen and Knudsen, {Anders Nicolai} and Larsen, {Kim Skak}",

year = "2015",

doi = "10.1142/S0129054115500264",

language = "English",

volume = "26",

pages = "477--486",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

publisher = "World Scientific",

number = "4",

}

TY - JOUR

T1 - Soccer is Harder Than Football

AU - Christensen, Jan

AU - Knudsen, Anders Nicolai

AU - Larsen, Kim Skak

PY - 2015

Y1 - 2015

N2 - It is known that deciding whether or not a team in a soccer tournament in progress can still win or, more generally, can obtain a certain position is NP-complete. We show that deciding whether or not a team is guaranteed a certain minimum position is coNP-complete. We also show that deciding with regards to goal difference, the standard tie-breaker for teams having the same number of points, whether or not a team can reach a certain position is NP-complete.

AB - It is known that deciding whether or not a team in a soccer tournament in progress can still win or, more generally, can obtain a certain position is NP-complete. We show that deciding whether or not a team is guaranteed a certain minimum position is coNP-complete. We also show that deciding with regards to goal difference, the standard tie-breaker for teams having the same number of points, whether or not a team can reach a certain position is NP-complete.

U2 - 10.1142/S0129054115500264

DO - 10.1142/S0129054115500264

M3 - Journal article

SN - 0129-0541

VL - 26

SP - 477

EP - 486

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 4

ER -

Soccer is Harder Than Football

Abstract

Documents & Links

Fingerprint

Cite this