Retrograde Chess. It is $PSPACE$-complete if you are allowed to have arbitrarily many kings and none of them can be in check at any time. If no (or only one per player) kings are allowed, it is known ...

It depends on how you define "solvable via network flows". If you allow the preprocessing step to take arbitrarily long, then anything is solvable using network flows by simply solving it an then ...

The trivial upper bound of $2^n$ (on a graph with $n$ vertices) is as tight as you can get, since a graph that has no edges does indeed have $2^n$ independent sets.
No, it is undecidable. Imagine a TM that outputs a sequence $0.1111\ldots$ that may be finite or not. If it is finite, the conversion algorithm should give some fraction like $\frac{11\ldots11}{10\... View answer Accepted answer 2 votes Yes. If the graph is regular there is a trivial scheme. Fix some ordering of the edges, and define$f(v)$to be$0$at the corresponding position of a particular edge if$v$is not incident to that ... View answer Accepted answer 2 votes The procedure maps each permutation of the vertices to some orientation of the graph whose topological ordering of the vertices is consistent with the permutation. Every acyclic orientation of the ... View answer Accepted answer 1 votes With only a polynomial amount of memory, a program that terminates can run for at most exponential time. This is because there are only exponentially many states (i.e. a combination of tape content (... View answer Accepted answer 0 votes This problem can be solved using a fairly standard dynamic programming approach, in time$O(n\cdot \Sigma_{w\in L} |w|)\$. This is not counting the complexity of big number arithmetic, which would ...