×

Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. (English) Zbl 1321.68274


MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C65 Hypergraphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Achlioptas, D. and Moore, C. 2007. Randomk-SAT: Two moments suffice to cross a sharp threshold.SIAM J. Comput. 36, 3, 740–762. · Zbl 1120.68096 · doi:10.1137/S0097539703434231
[2] Achlioptas, D. and Peres, Y. 2004. The threshold for randomk-SAT is 2klog2 − O(k).J. Amer. Math. Soc. 17, 4, 947–973. · Zbl 1093.68075 · doi:10.1090/S0894-0347-04-00464-3
[3] Alon, N. 2002. Testing subgraphs in large graphs.Rand. Struct. Algor. 21, 3–4, 359–370. · Zbl 1027.68095
[4] Alon, N., Fischer, E., Krivelevich, M., and Szegedy, M. 2000. Efficient testing of large graphs.Combinatorica 20, 4, 451–476. · Zbl 1052.68096 · doi:10.1007/s004930070001
[5] Alon, N., Kaufman, T., Krivelevich, M., and Ron, D. 2008. Testing triangle-freeness in general graphs.SIAM J. Disc. Math. 22, 2, 786–819. · Zbl 1163.68018 · doi:10.1137/07067917X
[6] Alon, N. and Shapira, A. 2004. Testing subgraphs in directed graphs.J. Comput. Syst. Sci. 69, 3, 354–382. · Zbl 1084.68087 · doi:10.1016/j.jcss.2004.04.008
[7] Alon, N. and Shapira, A. 2005. Linear equations, arithmetic progressions and hypergraph property testing.Theory Comput. 1, 1, 177–216. · Zbl 1213.68422 · doi:10.4086/toc.2005.v001a009
[8] Alon, N. and Shapira, A. 2006. A characterization of easily testable induced subgraphs.Combinat. Probab. Comput. 15, 6, 791–805. · Zbl 1318.68191 · doi:10.1017/S0963548306007759
[9] Arora, S. and Barak, B. 2009.Computational Complexity: A Modern Approach. Cambridge University Press, New York. · Zbl 1193.68112 · doi:10.1017/CBO9780511804090
[10] Behrend, F. A. 1946. On sets of integers which contain no three terms in arithmetic progression.Proc. Nat. Acad. Sci. 32, 12, 331–332. · Zbl 0060.10302 · doi:10.1073/pnas.32.12.331
[11] Binkele-Raible, D., Fernau, H., Fomin, F. V., Lokshtanov, D., Saurabh, S., and Villanger, Y. 2012. Kernel(s) for problems with no kernel: On out-trees with many leaves.ACM Trans. Algor. 8, 4, 38. · Zbl 1295.68120
[12] Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. 2009a. On problems without polynomial kernels.J. Comput. Syst. Sci. 75, 8, 423–434. · Zbl 1192.68288 · doi:10.1016/j.jcss.2009.04.001
[13] Bodlaender, H. L., Thomassé, S., and Yeo, A. 2009b. Kernel bounds for disjoint cycles and disjoint paths. InProceedings of the 17th Annual European Symposium on Algorithms (ESA’09). Lecture Notes in Computer Science, vol. 5757, Springer, 635–646. · Zbl 1256.68081
[14] Buhrman, H. and Hitchcock, J. M. 2008. NP-hard sets are exponentially dense unless NP is contained in coNP/poly. InProceedings of the 23rd IEEE Conference on Computational Complexity (CCC’08). IEEE Computer Society, 1–7.
[15] Buss, J. F. and Goldsmith, J. 1993. Nondeterminism within P.SIAM J. Comput. 22, 3, 560–572. · Zbl 0773.68031 · doi:10.1137/0222038
[16] Calabro, C., Impagliazzo, R., and Paturi, R. 2006. A duality between clause width and clause density for SAT. InProceedings of the 21st IEEE Conference on Computational Complexity (CCC’06). IEEE Computer Society, 252–260.
[17] Chandra, A. K., Furst, M. L., and Lipton, R. J. 1983. Multi-party protocols. InProceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC’83). ACM, 94–99.
[18] Chen, Y., Flum, J., and Müller, M. 2007. Lower bounds for kernelizations. Tech report TR07-137, Electronic Colloquium on Computational Complexity (ECCC).
[19] Chen, Y., Flum, J., and Müller, M. 2011. Lower bounds for kernelizations and other preprocessing procedures.Theory Comput. Syst. 48, 4, 803–839. · Zbl 1234.68118
[20] Cook, S. A. 1971. The complexity of theorem-proving procedures. InProceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC’71). ACM, 151–158.
[21] Coppersmith, D. and Winograd, S. 1990. Matrix multiplication via arithmetic progressions.J. Symb. Computat. 9, 3, 251–280. · Zbl 0702.65046 · doi:10.1016/S0747-7171(08)80013-2
[22] Davie, A. M. and Stothers, A. J. 2013. Improved bound for complexity of matrix multiplication.Proc. Roy. Soc. Edinburgh: Sect. A, Mathematics 143, 2, 351–369. · Zbl 1276.65024
[23] Dell, H. and Marx, D. 2012. Kernelization of packing problems. InProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). SIAM, 68–81.
[24] Dinur, I. 2007. The PCP theorem by gap amplification.J. ACM 54, 3, 12. · Zbl 1292.68074
[25] Dom, M., Lokshtanov, D., and Saurabh, S. 2009. Incompressibility through colors and IDs. InProceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP’09). Lecture Notes in Computer Science, vol. 5555, Springer, 378–389. · Zbl 1248.68243
[26] Downey, R. G. and Fellows, M. R. 1999.Parameterized Complexity. Springer New York. · doi:10.1007/978-1-4612-0515-9
[27] Drucker, A. 2012. New limits to classical and quantum instance compression. InProceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS’12). 609–618.
[28] Elkin, M. 2011. An improved construction of progression-free sets.Israel J. Math. 184, 1, 93–128. · Zbl 1280.11008 · doi:10.1007/s11856-011-0061-1
[29] Erdős, P. and Rado, R. 1960. Intersection theorems for systems of sets.J. Lond. Math. Soc. 35, 85–90. · Zbl 0103.27901
[30] Fellows, M. R., Guo, J., Moser, H., and Niedermeier, R. 2011. A generalization of Nemhauser and Trotter’s local optimization theorem.J. Comput. Syst. Sci. 77, 6, 1141–1158. · Zbl 1235.68081 · doi:10.1016/j.jcss.2010.12.001
[31] Flum, J. and Grohe, M. 2006.Parameterized Complexity Theory. Springer.
[32] Fortnow, L. and Santhanam, R. 2011. Infeasibility of instance compression and succinct PCPs for NP.J. Comput. Syst. Sci. 77, 1, 91–106. · Zbl 1233.68144 · doi:10.1016/j.jcss.2010.06.007
[33] Friedgut, E. and Bourgain, J. 1999. Sharp thresholds of graph properties, and thek-SAT problem.J. Amer. Math. Soc. 12, 4, 1017–1054. · Zbl 0932.05084 · doi:10.1090/S0894-0347-99-00305-7
[34] Goldreich, O. 2008.Computational Complexity: A Conceptual Perspective. ACM New York. · Zbl 1154.68056 · doi:10.1017/CBO9780511804106
[35] Goldreich, O., Goldwasser, S., and Ron, D. 1998. Property testing and its connection to learning and approximation.J. ACM 45, 4, 653–750. · Zbl 1065.68575 · doi:10.1145/285055.285060
[36] Green, B. and Wolf, J. 2010. A note on Elkins improvement of Behrends construction. InAdditive Number Theory, Springer, 141–144. · Zbl 1261.11013 · doi:10.1007/978-0-387-68361-4_9
[37] Guo, J. and Niedermeier, R. 2007. Invitation to data reduction and problem kernelization.SIGACT News 38, 1, 31–45. · doi:10.1145/1233481.1233493
[38] Harnik, D. and Naor, M. 2010. On the compressibility of NP instances and cryptographic applications.SIAM J. Comput. 39, 5, 1667–1713. · Zbl 1207.68162 · doi:10.1137/060668092
[39] Håstad, J. and Wigderson, A. 2003. Simple analysis of graph tests for linearity and PCP.Rand. Struct. Algor. 22, 2, 139–160. · Zbl 1064.68070
[40] Hemaspaandra, L. A., Hoene, A., Naik, A. V., Ogihara, M., Selman, A. L., Thierauf, T., and Wang, J. 1995. Nondeterministically selective sets.Int. J. Found. Comput. Sci. 6, 4, 403–416. · Zbl 0843.68031 · doi:10.1142/S0129054195000214
[41] Impagliazzo, R., Paturi, R., and Zane, F. 2001. Which problems have strongly exponential complexity?J. Comput. Syst. Sci. 63, 4, 512–530. · Zbl 1006.68052 · doi:10.1006/jcss.2001.1774
[42] Karp, R. M. 1972. Reducibility among combinatorial problems.Complex. Comput. Computat. 43, 85–103. · doi:10.1007/978-1-4684-2001-2_9
[43] Ko, K.-I. 1983. On self-reducibility and weak P-selectivity.J. Comput. Syst. Sci. 26, 2, 209–221. · Zbl 0519.68062 · doi:10.1016/0022-0000(83)90013-2
[44] Kratsch, S. 2012. Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem. InProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). SIAM, 114–122.
[45] Kratsch, S., Philip, G., and Ray, S. 2014. Point line cover: The easy kernel is essentially tight. InProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14). SIAM, 1596–1606. · Zbl 1423.68547
[46] Kratsch, S. and Wahlström, M. 2010. Preprocessing of min ones problems: A dichotomy. InProceedings of the 37th Colloquium on Automata, Languages and Programming (ICALP’10). Lecture Notes in Computer Science, vol. 6198, Springer, 653–665.
[47] Kratsch, S. and Wahlström, M. 2013. Two edge modification problems without polynomial kernels.Disc. Optim. · Zbl 1273.68181
[48] Krishnamoorthy, M. S. and Deo, N. 1979. Node-deletion NP-complete problems.SIAM J. Comput. 8, 4, 619–625. · Zbl 0423.05039 · doi:10.1137/0208049
[49] Levin, L. A. 1973. Universal search problems (Russian: Universal’nye perebornye zadachi).Prob. Inf. Trans.(Russian: Problemy Peredachi Informatsii)9, 3, 265–266.
[50] Lewis, J. M. and Yannakakis, M. 1980. The node-deletion problem for hereditary properties is NP-complete.J. Comput. Syst. Sci. 20, 2, 219–230. · Zbl 0436.68029 · doi:10.1016/0022-0000(80)90060-4
[51] Niedermeier, R. 2006.Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford, UK. · Zbl 1095.68038 · doi:10.1093/acprof:oso/9780198566076.001.0001
[52] Ruzsa, I. Z. and Szemerédi, E. 1978. Triple systems with no six points carrying three triangles. InCombinatorics (Proceedings of the 5th Hungarian Colloquium, Keszthely, 1976), Vol. II, Colloquia Mathematica Societatis János Bolyai, vol. 18, North-Holland, Amsterdam, 939–945.
[53] Salem, R. and Spencer, D. C. 1942. On sets of integers which contain no three terms in arithmetical progression.Proc. Nat. Acad. Sci. 28, 12, 561–563. · Zbl 0060.10301 · doi:10.1073/pnas.28.12.561
[54] Stothers, A. J. 2010. On the complexity of matrix multiplication. Ph.D. thesis, University of Edinburgh.
[55] Thomassé, S. 2010. A 4k2 kernel for feedback vertex set.ACM Trans. Algor. 6, 2, 32:1–32:8.
[56] Vassilevska Williams, V. 2012. Multiplying matrices faster than Coppersmith–Winograd. InProceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC’12). ACM, 887–898. · Zbl 1286.65056
[57] Wegener, I. 1987.The Complexity of Boolean Functions. B. G. Teubner, and John Wiley & Sons. · Zbl 0623.94018
[58] Yap, C.-K. 1983. Some consequences of non-uniform conditions on uniform classes.Theoret. Comput. Sci. 26, 3, 287–300. · Zbl 0541.68017 · doi:10.1016/0304-3975(83)90020-8
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.