0
$\begingroup$

Is there a polynomial-time algorithm for distribution of clauses of arbitrary symbols (i.e. similar to multiplication distributing over addition)? For simplicity, let's assume the distributive operation is concatenation and the symbols are letters in the English alphabet. For example, the clause (a b c) distributed with the clause (d e f) would result in: ad ae af bd be bf cd ce cf. The clauses need not be the same length, but they are here for simplicity. It's clear that the length of the result grows exponentially with respect to the amount of clauses, but does that mean any algorithm to generate the result must then be in exp-time? Or is there a more efficient way of generating such results?

$\endgroup$
2
  • $\begingroup$ Please define what you mean by "distribution of clauses". An example is not a substitute for a general specification. What are the inputs, and what is the desired output? $\endgroup$
    – D.W.
    Oct 11 at 4:27
  • $\begingroup$ Apologies, I thought what I gave would suffice. Essentially, it would be similar to multiplication distributing across addition. Each clause would contain an arbitrary number of characters, and concatenations would be generated by selecting one character from each clause, with all possible concatenations being the final output. Again, the process is similar to that of multiplication distributing across addition. $\endgroup$ Oct 11 at 12:27
1
$\begingroup$

If the output of the algorithm takes exponential space, then any algorithm must take exponential time. It takes at least N steps of computation even to output N characters (even ignoring the time it takes to figure out what to output), so the length of the output is a lower bound on the running time of the algorithm.

$\endgroup$

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.