Thread: Searching for new challenges

For a bit of low-level fun, try Core War - Wikipedia, the free encyclopedia

http://en.wikipedia.org/wiki/Go_(game) has a game tree which is far bushier than a chess game tree

Note that both chess and Go are two-person zero sum games with full information. Hence, there's always an optimal algorithm. In particular, there's the Minimax-algorithm, which is always optimal, but slightly inefficient on our current machines.

If you're interested in more challenging problems, check out the following two:

1)
Last Friday I've been told of an interesting open question:

Consider MICB, the problem of finding a minimal integral cycle basis in graphs. So far, it is known that MICB is NP-hard.

Question: is MICB NP-complete?

Find a proof or show the converse by finding a P-complete algorithm which computes a solution.

If you find a solution, please let me know.


2)
Today I discovered the following problem. It seems pretty easy, but given that it took two years from the release of the first Malbolge interpreter to the first Malbolge program (a Hello-World-program), it's probably a bit harder than it looks at first sight.

It is not known whether Malbolge is Turing-complete. Proof that it's not or show the converse, e.g. by implementing a translator from any Turing-complete language to Malbolge. A nice candidate for such a Turing-complete language is BrainF, because of its extremely simple syntax and its very restricted set of operations.

I strongly believe that it's possible to implement such a translator, but the semantics of Malbolge turn this task into a horrible nightmare.


Greets,
Philip