Uniquely solvable puzzles

We know that most "interesting" one-player games (or puzzles) are NP-hard. Read as:

given a puzzle, it's hard to decide whether it has a solution or not.

This question (seemingly) has little to do with the following one:

given a puzzle which is guaranteed to have exactly one solution, compute the solution.

Note that the standard reduction techniques do not preserve the number of solutions (e.g. no UP-complete problem is known as of today). I know that if we drop "exactly" (and write "at least" instead), then we get the class TFNP. But I do not know how this class of "uniqely solvable" problems is called and I'm interested in the current state of the art in this topic :-)

I could use someone to collect and read the literature for me ;-)

Addition-substraction chains

While implementing yet another iterated squaring algorithm (yep, this one) and thinking on possible optimizations I've bounced into addition-substraction chains.

An addition-substraction chain for some positive integer N is a list of positive integers which

• begins with 1,
• all the other elements are either the sum or the difference of two earlier members (which can be same in the case of addition) of the list,
• ends with N.

For example, 1,2,4,8,16,32,64,60 is an addition-substraction chain of length 8 for 60.

The question is to determine the complexity of the following question: given an integer N, what is the length of the shortest addition-substraction chain for N?

(Of course it's somewhere around O(lgN).)

Fav Problem #2: R(5,5)

How many vertices can a graph G have at most such that no complete subgraph of 5 nodes appear neither in G, nor in its complement?

The answer is somewhere between 43 and 49.

For more details on Ramsey numbers see this:

http://en.wikipedia.org/wiki/Ramsey's_theorem

Decidability of dot-depth 2

The following problem is well-known and still open for around four decades in the TCS community.

Focusing only on the problem statement: a language L⊆Σ* is of dot-depth two if it is a Boolean combination of languages of the form Σ₁*a₁Σ₂*a₂...Σ_k*a_kΣ_k+1* for some Σ_i⊆Σ and a_i∈Σ. For example, (a+b)*a(b+c)*∩a*b(a+b)* is of dot-depth two.

The question: is the following problem decidable?

• Input: a finite automaton recognizing some language L.
• Output: is L of dot-depth two?

Note: for the case of piecewise testable languages, that is, the case with Σ_i=Σ for each i, there exist several polytime algorithms, the most recent being this one:

http://link.springer.com/chapter/10.1007%2F978-3-642-38771-5_26

It would be interesting to see whether this new proof can be changed to cover a broader class of languages.

Fav Problem #1: Directing partial automata

A partial automaton is a system M=(Q, A, δ ) with Q being the finite nonempty set of states, A being a finite nonempty alphabet and δ being a partial function from Q×A to Q. (meaning something like "if I'm in q and get the symbol a on input, I will be in q'." if δ(q,a)=q' and "if I'm in q and get the symbol a on input, I'm stuck." if δ(q,a) is undefined). Instead of δ(q,a) we often write simply qa.

The action is extended to words as usual, setting qua := (qu)a. Of course if qu is undefined, then so is qua .

A word w is a directing word of M if pw=qw is defined for each state p,q in Q. In other words, if M gets w on input, no matter in which state M is, after processing w it will be in a fixed state. M is called directable if it possesses at least one directing word.

The question can be stated as follows:

Given an n-state directable partial automaton, how long can be its shortest directing word at most?

Known bounds:

1. For each n there exists a directable n-state partial automaton whose shortest directing word has length Ω(3^n/3). See P.V. Martyugin, Lower bounds for length of carefully synchronizing words, Presented at Satellite Workshop on Words and Automata of the International Computer Science Symposium in Russia (CSR'06), St. Petersburg, 2006. Basically a ternary counter is simulated.
2. Every n-state directable partial automaton possesses a directing word of length O(n²·4^n/3). See here: http://dl.acm.org/citation.cfm?id=1570791

My intuition says 3^n/3  is closer to the solution..

Picture languages: is a given set of tiles a maximal code?

The following question is motivated by the recent results of this paper:

http://link.springer.com/chapter/10.1007%2F978-3-642-38771-5_6

A picture is a rectangular array of letters. Given a set S of pictures, let S* stand for the set of those pictures that can be "decomposed" into a composition of members of S as in the following example:

a b c c b a a a b

is a member of the star of S = {

a b

,

c a

,

b

}.

(For formal definitions, see the paper.) 

Now S is a code if every picture in S* can be decomposed in a unique way (with respect to S ofc).

The set S above is a code since there is at most one element of S fitting to the top-left cell of any labeled polyomino (if it's a, we have to use the first domino, if b, the third and if c, the second, iterate).

A code S is maximal if no proper superset of S is a code. (The above S is not maximal since by adding a horizontal domino (a c) we still get a code.)

The question is to determine the complexity of the following problem:

• input: a finite set S of pictures,
• output: YES iff S is a maximal code.

Alternatively, the input can be assumed to be a code.
From the results of the paper we know it's decidable. But is it in P? or coNP-hard?

Off we go

Hi there,

I've created this blog devoted to various problems in theoretical computer science.

The purpose of the posts here is threefold:

1. I wanted for a long time to have these things all together.
2. I hope it will serve as a basis for students to have some problems to work on if they wish. Students of Uni Szeged can always drop me a few lines, should they become interested in any of these problems -- I'm pretty sure we can arrange a BSc / MSc thesis based on any of these topics.
3. I plan to post (at least occasionaly) a few stories on partial results whenever I succeed to have some progress :) (and also maybe post every now and then on the failures :P ) Think of it as PR. (Theoretical computer science badly needs PR nowadays..)

For all of you readers, welcome and feel free to leave comments, suggestions, ideas etc -- I will be grateful for them.

Cheers,

--szabivan