arXiv Open Access 2020

Hard Problems That Quickly Become Very Easy

Barnaby Martin Daniël Paulusma Siani Smith

Lihat Sumber

Abstrak

A graph class is hereditary if it is closed under vertex deletion. We give examples of NP-hard, PSPACE-complete and NEXPTIME-complete problems that become constant-time solvable for every hereditary graph class that is not equal to the class of all graphs.

Topik & Kata Kunci

cs.CC

Penulis (3)

Barnaby Martin

Daniël Paulusma

Siani Smith

Format Sitasi

APA MLA BibTeX

Martin, B., Paulusma, D., Smith, S. (2020). Hard Problems That Quickly Become Very Easy. https://arxiv.org/abs/2012.09770

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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