What makes some instances of hard probems hard and others rather easy?

We all know that there exist easily solvable instances (with respect to some algorithm, at least) of NP-complete problems, e.g. sudoku puzzles found in daily newspapers etc. And there exist hard ones of course, from NP-hardness (check e.g. this one).
But what makes these instances "easy" and "hard"? A convenient answer is "it depends on the solver algorithm", but it seems to be a more universal notion.
For example, there is a well-known phase transition in the case of the randomly generated 3SAT instances: suppose we generate k clauses over n variables, each having three literals. Now,

• if k is less than 4.25n (approximately), then the generated formula is satisfiable with high probability due to underconstraintedness -- and most solvers can generate a solution within a low runtime;
• if k is more than 4.25n (again, approximately), then the generated formula is whp overconstained and most solvers can deduce a contradiction within a low runtime,
• however,
• if k is around 4.25n, then deciding whether the formula is satisfiable or not is hard for all the solvers available. (that's why benchmarks and testbeds are generated exactly this way, usually).

So, these generated instances are "universally hard" -- but what does universality mean here? Is there a mathematical notion for measuring hardness of problem instances?
Research in this direction can be used to have a better understanding for the structure of NP-hard problems.

Thus it's probably very, very hard.

Any willing BSc / MSc student there? ^_^

Cov(G) vs Rect(G)

Let G=(A,B,E) be a bipartite graph. Cov(G) stands for its biclicque weight: the total weight of a covering of G with bicliques, where the size of a biclique is the number of its vertices. Rect(G) stands for the edge count of the smallest directed graph (V,E') with A U B being a subset of V, and where for each a in A and b in B, b is accessible from a if and only if (a,b) is in E.

The question is, what's the exact relationship between Rect(G) and Cov(G)? Clearly Rect(G) <= Cov(G) <= Rect(G)², but we should close the gaps.

Largest semigroup of "nonpermutational" transformations

Let Tn be the set of all transformations of [n]={1,...,n} for each n>0. Tn is a semigroup with product being function composition, i.e. (fg)(x) := g(f(x)) for each f,g ∈ Tn and x ∈ A. A subsemigroup of Tn is a subset of Tn which is closed under composition.
Call a transformation f: A→A nonpermutational if f(B)={f(x): x∈B}=B implies |B| ≤ 1 for any B ⊆ A. (Equivalently, if A is finite, then f is nonpermutational if it has a unique fixed point Fix(f) and no more cycles saving the loop on Fix(f).)
The nonpermutational transformations of [n] do not form a semigroup. The question is, if T is a subsemigroup of Tn consisting of only nonpermutational transformations, how large can T be?

Partial results so far:

• For each n, there exists a semigroup of nonpermutational transformations having size ⌊e(n-1)!⌋. See http://arxiv.org/abs/1203.2873.
• We can show that the size of any such semigroup is at most n!. See http://arxiv.org/abs/1304.5714.

Probably there will be a follow-up on this subject soon -- stay tuned... ;-)

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