Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?

Question

Definitions:

An up down language is a language whose alphabet is a set of pairs, but not characters, of two characters, where the one character in the pair is the opposite of the other character in the pair.

Each word in the language is concatenation of some characters from the alphabet given in the pairs of the alphabet set.

An up down language is emptible if and only if you can empty it, so it becomes Φ phi, without getting an empty word, which is marked as ε epsilon, before by only doing the "reduce" action only.

The "reduce" action is an action which removes a pair from the alphabet and then removes all words from the language that own/contain one character in the removed pair and also removes the other character in the removed pair from all words that were left/remaining in the language (after the first removal) that own/contain the other character in the removed pair. As a result the language becomes a set with fewer/lesser shorter words. This way it is possible to empty the language by repeating this action, i.e. the "reduce" action only, but it is also possible to get an empty word, i.e. epsilon ε.

Summary/In conclusion:

When given non empty up down language that doesn't own/contain the empty word ε epsilon, your objectives are/goal is:

1. Get the empty language Φ phi, which is a must.
2. Do not get the empty word ε epsilon before, which is forbidden.
3. You can only do the "reduce" action as defined above to achieve the first objective 1.

Examples:

The following up down language is emptible:

L={abc,bxd,ye} where Σ={(a,z),(b,y),(c,x),(d,w),(e,v)}

Because

Reduce(b,L)={e} where Σ={(e,v)} Note that the words that owned/contained the letter 'b' were removed from the language and the letter 'y' was removed as well, because 'b' was paired with 'y', so the word "ye" was shorten to "e"

and

Reduce(e,{e})=Φ

I could get Φ without getting ε so the above up down language is indeed emptible

But the following up down language is not emptible:

L={ab,ay,zc,zx} where Σ={(a,z),(b,y),(c,x)}

Because:

Reduce(a,L)=L'={c,x} where Σ={(c,x)} again words with the letter 'a' were removed, but 'a' is paired with 'z', so the letter 'z' was removed as well and the word "zc" was shorten to "z" and the word "zx" was shorten to "x".

Reduce(c,L')={ε}, because the word "c" was removed and 'x' was paired with 'c', so the letter 'x' was removed as well. Because the only word left was "x" and 'x' was removed, so it became the empty or ε in other words. So this attempt was failure, because we didn't get Φ, but ε instead.

Of course it shouldn't say that the above up down language is not emptible, because I tried only one option. Instead of Reduce(c,L'), I could try Reduce(x,L') instead, but also Reduce(x,L')={ε}, because the word "x" was removed this time and "c" was remained, but 'x' is paired with 'c', so 'c' must be removed as well and thus "c" becomes ε. So again, I got ε, but not Φ. So starting with Reduce(a,L) wasn't the right choice. I could start with Reduce(b,L) or Reduce(c,L) or Reduce(x,L) or Reduce(y,L) or Reduce(z,L) instead. I won't try the other options, because this will take too long, but you can try and you will see that in the all options, you get ε, but not Φ

What I have tried already:

I wrote the following recursive algorithm/function/procedure, in pseudo code that is bit similar to C/C++, to determine whether or not the given up down language is emptible or not, where the algorithm/function/procedure "Reduce" modifies the given up down language and then returns a clone/copy of it without updating the original given up down language, in other words, it clones/copies the given up down language, modifies the clone/copy and then returns the clone/copy. Assume that there is garbage collector that frees up unused allocated memory:

bool MyIsEmptible(up_down_language udl)
{
    if (udl.IsEmpty)
        return true;
    if (udl.Owns(epsilon))
        return false;
    for each (pair 'p' in udl.alphabet)
       if (MyIsEmptible(Reduce(p,0,udl)) or MyIsEmptible(Reduce(p,1,udl)))
          return true;
    return false;
}

The above algorithm/function/procedure is working, because it iterates recursively over all the possible options, but the problem is that the time complexity of this algorithm/function/procedure is not polynomial in the worst case where the given up down language is not emptible, and the time complexity, in the worst case, is big O notation of multiplication/product of exponent of n by base 2 and factorial of n and this is too expensive.

Proof:

Assume that 'n' is the number of pairs in the alphabet. In the first iteration, the algorithm walks over all pairs and each pair twice for the first and its opposite the second character in the iterated pair, so right now the time complexity of this algorithm is Ω(2•n). But the recursive calls do exactly the same thing for n-1.

So the time complexity of this algorithm can be expressed as: T(n)=2•n•T(n-1)

This evaluates to: 2•n•2•(n-1)•T(n-2)=2²•n•(n-1)•T(n-2)=2ⁿ•n!

So

T(n) = O(2ⁿ•n!)

I believe that only greedy algorithm can solve this decision/search problem in polynomial time, but it will have to use some temporary data structure to accomplish this, so the space complexity of this algorithm is not O(1), but it can be polynomial.

Answer 1

Reduction from 3-SAT: a variable in 3-SAT becomes a character in your problem and is paired with its negation. Each clause becomes a word.

e.g.

• 3 SAT: (a,b,-c) && (-b,c) =>
• pairs: (a,-a), (b,-b), (c,-c).
• words: (a,b,-c), (-b,c)

Selecting a character in your problem means setting that literal to true in the 3-SAT instance. The corresponding clauses are removed (they are satisfied) and the remaining clauses that contain the negation of that character/literal have that literal removed, as those clauses need to be satisfied with one of the remaining literals.

It is NP-hard.