×

Tropical complexity, Sidon sets, and dynamic programming. (English) Zbl 1353.68103

Summary: Many dynamic programming algorithms for discrete 0-1 optimization problems are just special (recursively constructed) tropical \((\min,+)\) or \((\max,+)\) circuits. A problem is homogeneous if all its feasible solutions have the same number of ones. M. Jerrum and M. Snir [J. ACM 29, 874–897 (1982; Zbl 0485.68038)] proved that tropical circuit complexity of homogeneous problems coincides with the monotone arithmetic circuit complexity of the corresponding polynomials. So, lower bounds on the monotone arithmetic circuit complexity of these polynomials yield lower bounds on the tropical complexity of the corresponding optimization problems. But the situation with nonhomogeneous problems is entirely different: here the gap between their tropical and arithmetic complexities can be even exponential. In this paper, we improve two classical lower bounds for monotone arithmetic circuits – Schnorr’s bound and Hyafil-Valiant’s bound – and use these improvements to derive general lower bounds for the tropical circuit complexity of nonhomogeneous optimization problems. In particular, we show that optimization problems, whose sets of feasible solutions are cover free, have large tropical complexity.

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05D05 Extremal set theory
90C39 Dynamic programming

Citations:

Zbl 0485.68038

Software:

Algorithm 97
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon, {\it Explicit construction of exponential sized families of \(k\)-independent sets}, Discrete Math., 58 (1986), pp. 191-193. · Zbl 0588.05003
[2] R. Bellman, {\it On a routing problem}, Quart. Appl. Math., 16 (1958), pp. 87-90. · Zbl 0081.14403
[3] X. Chen, N. Kayal, and A. Wigderson, {\it Partial derivatives in arithmetic complexity and beyond}, Found. Trends Theor. Comput. Sci., 6 (2011), pp. 1-138. · Zbl 1278.68010
[4] J. Cilleruelo, {\it Sidon sets in \(N^d\)}, J. Combin. Theory Ser. A, 117 (2010), pp. 857-871. · Zbl 1246.11022
[5] P. Erdös, P. Frankl, and Z. Füredi, {\it Families of finite sets in which no set is covered by the union of two others}, J. Combin. Theory Ser. A, 33 (1982), pp. 158-166. · Zbl 0489.05003
[6] P. Erdös and E. Harzheim, {\it Congruent subsets of infinite sets of natural numbers}, J. Reine Angew. Math., 367 (1986), pp. 207-214. · Zbl 0575.10041
[7] P. Erdös and P. Turán, {\it On a problem of Sidon in additive number theory, and on some related problems}, J. Lond. Math. Soc. (2), 16 (1941), pp. 212-215. · Zbl 0061.07301
[8] R. Floyd, {\it Algorithm 97, shortest path}, Comm. ACM, 5 (1962), p. 345.
[9] L. Ford, {\it Network Flow Theory}, Technical report P-923, The Rand Corp., 1956.
[10] J. Friedman, {\it Constructing \(\mbox{O}(n \log n)\) size monotone formulae for the \(k\) th elementary symmetric polynomial of \(n\) boolean variables}, in 25th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Los Angeles, 1984, pp. 506-515.
[11] S. Gashkov, {\it On one method of obtaining lower bounds on the monotone complexity of polynomials}, Vestnik Moskov. Univ., Ser. 1 Math., Mekh, 5 (1987), pp. 7-13. · Zbl 0641.68057
[12] S. Gashkov and I. Sergeev, {\it A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials}, Sb. Math., 203 (2012), pp. 1411-1147. · Zbl 1270.68113
[13] D. Grigoriev and G. Koshevoy, {\it Complexity of tropical Schur polynomials}, J. Symbolic Comput., 74 (2016), pp. 46-54. · Zbl 1329.65060
[14] M. Held and R. M. Karp, {\it A dynamic programming approach to sequencing problems}, SIAM J. on Appl. Math., 10 (1962), pp. 196-210. · Zbl 0106.14103
[15] P. Hrubes and A. Yehudayoff, {\it Homogeneous formulas and symmetric polynomials}, Comput. Complexity, 20 (2011), pp. 559-578. · Zbl 1233.68230
[16] L. Hyafil, {\it On the parallel evaluation of multivariate polynomials}, SIAM J. Comput., 8 (1979), pp. 120-123. · Zbl 0408.68041
[17] M. Jerrum and M. Snir, {\it Some exact complexity results for straight-line computations over semirings}, J. ACM, 29 (1982), pp. 874-897. · Zbl 0485.68038
[18] S. Jukna, {\it Boolean Function Complexity: Advances and Frontiers}, Springer, Berlin, 2012. · Zbl 1235.94005
[19] S. Jukna, {\it Lower bounds for tropical circuits and dynamic programs}, Theory Comput. Syst., 57 (2015), pp. 160-194. · Zbl 1320.68093
[20] W. Kautz and R. Singleton, {\it Nonrandom binary superimposed codes}, IEEE Trans. Inform. Theory, 10 (1964), pp. 363-377. · Zbl 0133.12402
[21] J. Kollár, L. Rónyai, and T. Szabó, {\it Norm-graphs and bipartite Turán numbers}, Combinatorica, 16 (1996), pp. 399-406. · Zbl 0858.05061
[22] R. Lidl and H. Niederreiter, {\it Introduction to Finite Fields and their Applications.}, Cambridge University Press, Cambridge, 1986. · Zbl 0629.12016
[23] B. Lindström, {\it Determination of two vectors from the sum}, J. Combin. Theory Ser. B, 6 (1969), pp. 402-407. · Zbl 0169.32001
[24] B. Lindström, {\it On \(B_2\)-sequences of vectors}, J. Number Theory, 4 (1972), pp. 261-265. · Zbl 0235.10028
[25] E. Moore, {\it The shortest path through a maze}, in Proceedings of an Internatational Symposium on Switching Theory, Vol. II, Harvard Univ. Press, Cambridge, 1959, pp. 285-292.
[26] K. O’Bryant, {\it A complete annotated bibliography of work related to Sidon sequences}, Electr. J. Comb., 11 (2004), DS11.
[27] N. Pippenger, {\it On another Boolean matrix}, Theoret. Comput. Sci., 11 (1980), pp. 49-56. · Zbl 0429.94038
[28] R. Raz and A. Yehudayoff, {\it Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors}, J. Comput. System Sci., 77 (2011), pp. 167-190. · Zbl 1209.68382
[29] C. Schnorr, {\it A lower bound on the number of additions in monotone computations}, Theoret. Comput. Sci., 2 (1976), pp. 305-315. · Zbl 0342.68024
[30] R. Sengupta and H. Venkateswaran, {\it A lower bound for monotone arithmetic circuits computing 0-1 permanent}, Theoret. Comput. Sci., 209 (1998), pp. 389-398. · Zbl 0912.68056
[31] E. Shamir and M. Snir, {\it On the depth complexity of formulas}, Math. System Theory, 13 (1980), pp. 301-322. · Zbl 0445.68031
[32] A. Shpilka and A. Yehudayoff, {\it Arithmetic circuits: A survey of recent results and open questions}, Found. Trends Theor. Comput. Sci., 5 (2010), pp. 207-388. · Zbl 1205.68175
[33] P. Tiwari and M. Tompa, {\it A direct version of Shamir and Snir’s lower bounds on monotone circuit depth}, Inform. Process. Lett., 49 (1994), pp. 243-248. · Zbl 0795.68102
[34] L. Valiant, {\it Negation can be exponentially powerful}, Theoret. Comput. Sci., 12 (1980), pp. 303-314. · Zbl 0442.68030
[35] S. Warshall, {\it A theorem on boolean matrices}, J. ACM, 9 (1962), pp. 11-12. · Zbl 0118.33104
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.