Tom van der Zanden
  • Member for 7 years, 2 months
  • Last seen more than a month ago
Problems not known to be PSPACE-complete
12 votes

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 ...

View answer
Characterizing the set of problems solvable via network flow
Accepted answer
7 votes

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 ...

View answer
Upper bound for number of independent sets
Accepted answer
5 votes

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.

View answer
For two representations of finite length of one computable number are there $P$-time algorithms that compute one from another
Accepted answer
3 votes

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
polytime transformation from a graph to a set of binary strings
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
An edge orientation procedure to generate all acyclic orientations of a graph
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
An algorithm for counting to Graham’s Number
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
A simple challenge
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 ...

View answer