arXiv Open Access 2014

TrackMania is NP-complete

Franck Dernoncourt

Lihat Sumber

Abstrak

We prove that completing an untimed, unbounded track in TrackMania Nations Forever is NP-complete by using a reduction from 3-SAT and showing that a solution can be checked in polynomial time.

Topik & Kata Kunci

cs.CC

Penulis (1)

Franck Dernoncourt

Format Sitasi

APA MLA BibTeX

Dernoncourt, F. (2014). TrackMania is NP-complete. https://arxiv.org/abs/1411.5765

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2014
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓