- wenn das Problem nicht in NP ist,
dann hat es keine polynomiell große Kodierung.
- wahrscheinliche Beispiele:
Suchprobleme mit (exponentiell) tiefen Bäumen,
z. B. Verschiebepuzzles
(Rushhour, Atomix, Lunar Lockout (?))
- Markus Holzer, Stefan Schwoon:
Assembling Molecules in Atomix in Hard,
TCS 2003, http://dblp.uni-trier.de/rec/bibtex/journals/tcs/HolzerS04
- PSPACE-hardness ist offen für Lunar Lockout
2014-07-06
