nach oben

Theory of Computing Systems

Erschienen in:

01.07.2016

Holant Problems for 3-Regular Graphs with Complex Edge Functions

verfasst von: Michael Kowalczyk, Jin-Yi Cai

Erschienen in: Theory of Computing Systems | Ausgabe 1/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We prove a complexity dichotomy theorem for Holant problems on 3-regular graphs with an arbitrary complex-valued edge function. Three new techniques are introduced: (1) higher dimensional iterations in interpolation; (2) Eigenvalue Shifted Pairs, which allow us to prove that a pair of combinatorial gadgets in combination succeed in proving #P-hardness; and (3) algebraic symmetrization, which significantly lowers the symbolic complexity of the proof for computational complexity. Using holographic reductions the classification theorem also applies to problems beyond the basic model.

Vorheriger Artikel The Update Complexity of Selection and Related Problems

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 "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

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

Technically, computational complexity involving complex or real numbers should, in the Turing model, be restricted to computable numbers. In other models such as the Blum-Shub-Smale model [1] no such restrictions are needed. Our results are not sensitive to the exact model of computation.

The term Holant was first introduced by Valiant in [22] for a related quantity, which can be viewed as a special case.

Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation. Springer New York, Inc. (1998)

Bulatov, A.A., Grohe, M.: The complexity of partition functions. Theor. Comput. Sci. 348(2-3), 148–186 (2005)MathSciNetCrossRefMATH

Cai, J.Y., Chen, X., Lu, P.: Graph homomorphisms with complex values: a dichotomy theorem. SIAM J. Comput. 42(3), 924–1029 (2013)MathSciNetCrossRefMATH

Cai, J.Y., Kowalczyk, M.: Spin systems on k-regular graphs with complex edge functions. Theor. Comput. Sci. 461(1), 2–16 (2012)MathSciNetCrossRefMATH

Cai, J.Y., Kowalczyk, M.: Partition functions on k-regular graphs with {0, 1}-vertex assignments and real edge functions. Theor. Comput. Sci. 494, 63–74 (2013)MathSciNetCrossRefMATH

Cai, J.Y., Lu, P.: Holographic algorithms: from art to science. J. Comput. Syst. Sci. 77(1), 41–61 (2011)MathSciNetCrossRefMATH

Cai, J.Y., Lu, P., Xia, M.: Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. In: FOCS ’08: proceedings of the 49th annual ieee symposium on foundations of computer science, pp 644–653. IEEE Computer Society, Washington (2008)

Cai, J.Y., Lu, P., Xia, M.: A computational proof of complexity of some restricted counting problems. Theor. Comput. Sci. 412(23), 2468–2485 (2011)MathSciNetCrossRefMATH

Cai, J.Y., Lu, P., Xia, M.: Holographic reduction, interpolation and hardness. Comput. Complex. 21(4), 573–604 (2012)MathSciNetCrossRefMATH

10.

Cai, J.Y., Lu, P., Xia, M.: Holographic algorithms by Fibonacci gates. Linear Algebra Appl. 438(2), 690–707 (2013)MathSciNetCrossRefMATH

11.

Dyer, M.E., Goldberg, L.A., Paterson, M.: On counting homomorphisms to directed acyclic graphs, vol. 54 (2007)

12.

Dyer, M.E., Greenhill, C.S.: The complexity of counting graph homomorphisms. Random Struct. Algorithms 17(3–4), 260–289 (2000)MathSciNetCrossRefMATH

13.

Goldberg, L.A., Grohe, M., Jerrum, M., Thurley, M.: A complexity dichotomy for partition functions with mixed signs. SIAM J. Comput. 39(7), 3336–3402 (2010)MathSciNetCrossRefMATH

14.

Hell, P., Nešetřil, J.: On the complexity of H-coloring. Journal of Combinatorial Theory, Series B 48(1), 92–110 (1990)MathSciNetCrossRefMATH

15.

Kowalczyk, M.: Classification of a class of counting problems using holographic reductions. In: Ngo, H.Q. (ed.) COCOON, lecture notes in computer science, vol. 5609, pp 472–485. Springer (2009)

16.

Kowalczyk, M., Cai, J.Y.: Holant Problems for Regular Graphs with Complex Edge Functions. In: Marion, J.Y., Schwentick, T. (eds.) STACS 2010, pp 525–536 (2010)

17.

Tarski, A.: A Decision Method for Elementary Algebra and Geometry, 2nd edn. University of California Press, Berkeley (1951)

18.

Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput. 31(2), 398–427 (2001)MathSciNetCrossRefMATH

19.

Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189–201 (1979)MathSciNetCrossRefMATH

20.

Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410–421 (1979)MathSciNetCrossRefMATH

21.

Valiant, L.G.: Quantum circuits that can be simulated classically in polynomial time. SIAM J. Comput. 31(4), 1229–1254 (2002)MathSciNetCrossRefMATH

22.

Valiant, L.G.: Holographic algorithms. SIAM J. Comput. 37(5), 1565–1594 (2008). (A preliminary version appeared in FOCS 2004)MathSciNetCrossRefMATH

23.

Xia, M., Zhang, P., Zhao, W.: Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci. 384(1), 111–125 (2007)MathSciNetCrossRefMATH

Titel: Holant Problems for 3-Regular Graphs with Complex Edge Functions
verfasst von: Michael Kowalczyk
Jin-Yi Cai
Publikationsdatum: 01.07.2016
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 1/2016
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-016-9671-7

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 "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2016

On the Stability of Generalized Second Price Auctions with Budgets

The Computational Complexity of Iterated Elimination of Dominated Strategies

A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness

On the Parameterised Complexity of String Morphism Problems

The Update Complexity of Selection and Related Problems

Complexity of Approximating CSP with Balance / Hard Constraints