nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps

verfasst von : Libor Barto

Erschienen in: Fundamentals of Computation Theory

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

What makes a computational problem easy (e.g., in P, that is, solvable in polynomial time) or hard (e.g., NP-hard)? This fundamental question now has a satisfactory answer for a quite broad class of computational problems, so called fixed-template constraint satisfaction problems (CSPs) – it has turned out that their complexity is captured by a certain specific form of symmetry. This paper explains an extension of this theory to a much broader class of computational problems, the promise CSPs, which includes relaxed versions of CSPs such as the problem of finding a 137-coloring of a 3-colorable graph.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Retraction Note to: Complete Disjoint CoNP-Pairs but No Complete Total Polynomial Search Problems Relative to an Oracle

Nächstes Kapitel Some Observations on Dynamic Random Walks and Network Renormalization

Here we should rather say a hypergraph whose hyperedges have size at most 3 because of conjuncts of the form \(3NAE_k(x,x,y)\) or \(3NAE_k(x,x,x)\). Let us ignore this minor technical imprecision.

Their conjecture is equivalent but was, of course, originally stated in a different language – the significance of minor conditions in CSPs was identified much later.

Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501–555 (1998). https://doi.org/10.1145/278298.278306MathSciNetCrossRefMATH

Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70–122 (1998). https://doi.org/10.1145/273865.273901MathSciNetCrossRefMATH

Austrin, P., Guruswami, V., Håstad, J.: (2+\(\epsilon \))-sat is NP-hard. SIAM J. Comput. 46(5), 1554–1573 (2017). https://doi.org/10.1137/15M1006507MathSciNetCrossRefMATH

Barto, L.: Promises make finite (constraint satisfaction) problems infinitary. In: LICS (2019, to appear)

Barto, L., Bulín, J., Krokhin, A.A., Opršal, J.: Algebraic approach to promise constraint satisfaction (2019, in preparation)

Barto, L., Krokhin, A., Willard, R.: Polymorphisms, and how to use them. In: Krokhin, A., Živný, S. (eds.) The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl Follow-Ups, vol. 7, pp. 1–44. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2017). https://doi.org/10.4230/DFU.Vol7.15301.1

Barto, L., Opršal, J., Pinsker, M.: The wonderland of reflections. Isr. J. Math. 223(1), 363–398 (2018). https://doi.org/10.1007/s11856-017-1621-9MathSciNetCrossRefMATH

Birkhoff, G.: On the structure of abstract algebras. Math. Proc. Camb. Philos. Soc. 31(4), 433–454 (1935). https://doi.org/10.1017/S0305004100013463CrossRefMATH

Bodirsky, M.: Constraint satisfaction problems with infinite templates. In: Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.) Complexity of Constraints. LNCS, vol. 5250, pp. 196–228. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92800-3_8CrossRefMATH

10.

Bodnarchuk, V.G., Kaluzhnin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for post algebras. I. Cybernetics 5(3), 243–252 (1969). https://doi.org/10.1007/BF01070906MathSciNetCrossRef

11.

Bodnarchuk, V.G., Kaluzhnin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for Post algebras. II. Cybernetics 5(5), 531–539 (1969)CrossRef

12.

Brakensiek, J., Guruswami, V.: New hardness results for graph and hypergraph colorings. In: Raz, R. (ed.) 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 50, pp. 14:1–14:27. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016). https://doi.org/10.4230/LIPIcs.CCC.2016.14

13.

Brakensiek, J., Guruswami, V.: Promise constraint satisfaction: Algebraic structure and a symmetric boolean dichotomy. ECCC Report No. 183 (2016)

14.

Brakensiek, J., Guruswami, V.: Promise constraint satisfaction: Structure theory and a symmetric boolean dichotomy. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp. 1782–1801. Society for Industrial and Applied Mathematics, Philadelphia (2018). http://dl.acm.org/citation.cfm?id=3174304.3175422

15.

Brakensiek, J., Guruswami, V.: An algorithmic blend of LPs and ring equations for promise CSPs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, 6–9 January 2019, pp. 436–455 (2019). https://doi.org/10.1137/1.9781611975482.28CrossRef

16.

Bulatov, A., Jeavons, P., Krokhin, A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34(3), 720–742 (2005). https://doi.org/10.1137/S0097539700376676MathSciNetCrossRefMATH

17.

Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 319–330, October 2017. https://doi.org/10.1109/FOCS.2017.37

18.

Bulín, J., Krokhin, A., Opršal, J.: Algebraic approach to promise constraint satisfaction. In: Proceedings of the 51st Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2019). ACM, New York (2019). https://doi.org/10.1145/3313276.3316300

19.

Dinur, I., Regev, O., Smyth, C.: The hardness of 3-uniform hypergraph coloring. Combinatorica 25(5), 519–535 (2005). https://doi.org/10.1007/s00493-005-0032-4MathSciNetCrossRefMATH

20.

Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput. 28(1), 57–104 (1998). https://doi.org/10.1137/S0097539794266766MathSciNetCrossRefMATH

21.

Geiger, D.: Closed systems of functions and predicates. Pacific J. Math. 27, 95–100 (1968). https://doi.org/10.2140/pjm.1968.27.95MathSciNetCrossRefMATH

22.

Håstad, J.: Some optimal inapproximability results. J. ACM 48(4), 798–859 (2001). https://doi.org/10.1145/502090.502098MathSciNetCrossRefMATH

23.

Huang, S.: Improved hardness of approximating chromatic number. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) APPROX/RANDOM -2013. LNCS, vol. 8096, pp. 233–243. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40328-6_17CrossRef

24.

Jeavons, P.: On the algebraic structure of combinatorial problems. Theor. Comput. Sci. 200(1–2), 185–204 (1998). https://doi.org/10.1016/S0304-3975(97)00230-2MathSciNetCrossRefMATH

25.

Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. J. ACM 44(4), 527–548 (1997). https://doi.org/10.1145/263867.263489MathSciNetCrossRefMATH

26.

Krokhin, A., Živný, S. (eds.): The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl Follow-Ups, vol. 7. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

27.

Lovász, L.: Kneser’s conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A 25(3), 319–324 (1978). https://doi.org/10.1016/0097-3165(78)90022-5MathSciNetCrossRefMATH

28.

Pippenger, N.: Galois theory for minors of finite functions. Discrete Math. 254(1), 405–419 (2002). https://doi.org/10.1016/S0012-365X(01)00297-7MathSciNetCrossRefMATH

29.

Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC 1978, pp. 216–226. ACM, New York (1978). https://doi.org/10.1145/800133.804350

30.

Zhuk, D.: A proof of CSP dichotomy conjecture. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 331–342, October 2017. https://doi.org/10.1109/FOCS.2017.38

Titel: Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps
verfasst von: Libor Barto
Verlag: Springer International Publishing
Buch: Fundamentals of Computation Theory
Print ISBN: 978-3-030-25026-3

Electronic ISBN: 978-3-030-25027-0

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-25027-0_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner