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?
$\begingroup$
$\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, 2021 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$– user3670473Oct 11, 2021 at 12:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
