6
$\begingroup$

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)=22•n•(n-1)•T(n-2)=2n•n!

So

T(n) = O(2n•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.

$\endgroup$
  • 3
    $\begingroup$ Your question looks interesting, but the formulation used is a bit non-standard, which could lead to to confusion. So, to be clear: A language $L$ is by definition a set of strings over an alphabet $\Sigma$, which means the words in $L$ must be strings of pairs if $\Sigma$ contains pairs. So, I think your problem can be phrased as: given a language is $L$ over alphabet $\Sigma$ and a set of pairs $P$ of characters in $\Sigma$, determine whether $L$ can be 'emptied' by reducing with the pairs in $P$. Is this interpretation correct? $\endgroup$ – Discrete lizard Jun 17 '17 at 21:51
  • 1
    $\begingroup$ Do you have a particular reason to believe only a greedy algorithm could solve this problem in polynomial time? $\endgroup$ – Discrete lizard Jun 17 '17 at 21:53
  • $\begingroup$ By the way, did you notice my examples? I wrote two examples in my question, where the first language is 'emptible' and the other is not. This should explain as good as possible what my question asks. $\endgroup$ – Farewell Stack Exchange Jun 17 '17 at 22:36
  • $\begingroup$ If I understand correctly from your examples, the condition "the one character in the pair is the opposite of the other character in the pair" means two things: (1) the characters belong to {a, ..., z} (2) the pairs are of the form ('a'+k, 'z'-k) for some k in {0,...,25}. But then there are at most 26 possible pairs and your complexity question doesn't make sense anymore. Did I misunderstood something? $\endgroup$ – J.-E. Pin Jun 21 '17 at 8:09
  • $\begingroup$ "the one character in the pair is the opposite of the other character in the pair" this is correct, but characters are not necessarily letters/ alpha characters, but they also can be digits, punctuations, any symbol you can imagine. In my examples, it seems that the pairs are of the form ('a'+k,'z'-k), so yes pairs can be in this form, but not necessarily, but in each pair, you can determine what will be the first character in and what will be the other). The cardinality of alphabet can be any finite number, not at most 26. Why my complexity question doesn't make sense anymore? $\endgroup$ – Farewell Stack Exchange Jun 21 '17 at 15:50
6
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just NP-hard? But I thought that 3-SAT is NP-Complete, that means it's not only NP-hard, but also NP. So this problem should not be NP-complete then? Solution to this problem should be solution to the 3-SAT problem and also to k-SAT problem, because also k-SAT can be reduced to this problem. Anyway this is great answer. This problem can be added to the list of the known NP-complete problems, so computer scientists can start thinking about it. If one find polynomial time solution to this problem, this will lead to the proof that P=NP, right? $\endgroup$ – Farewell Stack Exchange Jun 27 '17 at 14:49
  • 1
    $\begingroup$ Everything you say is correct. Also, it's indeed NP-complete and therefore also NP-hard. I was only mentioning the NP-hard part because that's enough to indicate that probably no Polynomial solution exists (unless P=NP) $\endgroup$ – Albert Hendriks Jun 27 '17 at 14:55
  • 1
    $\begingroup$ I understand, but at least it worth a try anyway, because does not exist a proof that does not exist Polynomial solution to this problem. I just want to see the same problem in another view. $\endgroup$ – Farewell Stack Exchange Jun 27 '17 at 15:44
  • 1
    $\begingroup$ I've been doing the same for 16 years. I probably won't find a solution anymore, but I learned a lot about algorithms and complexity theory and it gave me a lot of useful side projects. I wish you all the best... $\endgroup$ – Albert Hendriks Jun 27 '17 at 19:55
  • $\begingroup$ What do you mean by saying "I've been doing the same for 16 years."? Do you mean that you also invented new NP-Complete problems based on the SAT problem? Thank you for wishing for me all the best by the way. I am grateful. $\endgroup$ – Farewell Stack Exchange Jun 27 '17 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.