nach oben

Theory of Computing Systems

Erschienen in:

01.06.2022

Nonuniform Reductions and NP-Completeness

verfasst von: John M. Hitchcock, Hadi Shafei

Erschienen in: Theory of Computing Systems | Ausgabe 4/2022

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP-completeness, obtaining both separations and upper bounds for nonuniform completeness vs uniform complessness in NP. Under various hypotheses, we obtain the following separations:

There is a set complete for NP under nonuniform many-one reductions, but not under uniform many-one reductions. This is true even with a single bit of nonuniform advice.

There is a set complete for NP under nonuniform many-one reductions with polynomial-size advice, but not under uniform Turing reductions. That is, polynomial nonuniformity cannot be replaced by a polynomial number of queries.

For any fixed polynomial p(n), there is a set complete for NP under uniform 2-truth-table reductions, but not under nonuniform many-one reductions that use p(n) advice. That is, giving a uniform reduction a second query makes it impossible to simulate by a nonuniform reduction with fixed polynomial advice.

There is a set complete for NP under nonuniform many-one reductions with polynomial advice, but not under nonuniform many-one reductions with logarithmic advice. This hierarchy theorem also holds for other reducibilities, such as truth-table and Turing.

We also consider uniform upper bounds on nonuniform completeness. Hirahara (2015) showed that unconditionally every set that is complete for NP under nonuniform truth-table reductions that use logarithmic advice is also uniformly Turing-complete. We show that under a derandomization hypothesis, every set that is complete for NP under nonuniform truth-table reductions is also uniformly truth-table complete.

Nächster Artikel Non-Existence of Stable Social Groups in Information-Driven Networks

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

Adleman, L.: Two theorems on random polynomial time. In: Proceedings of the 19th IEEE Symposium on Foundations of Computer Science, pp 75–83 (1978)

Agrawal, M.: Pseudo-random generators and structure of complete degrees. In: Proceedings of the Seventeenth Annual IEEE Conference on Computational Complexity, pp 139–147. IEEE Computer Society (2002)

Agrawal, M., Watanabe, O.: One-way functions and the Berman-Hartmanis conjecture. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, pp 194–202 (2009)

Allender, E.: When worlds collide: Derandomization, lower bounds, and Kolmogorov complexity. In: Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science, pp 1–15. Springer-Verlag (2001)

Allender, E.: The complexity of complexity. In: Computability and Complexity - Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, vol. 10010, pp 79–94 (2017)

Allender, E., Buhrman, H., Koucký, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. SIAM Journal on Computing 35, 1467–1493 (2006)MathSciNetCrossRef

Ambos-Spies, K., Mayordomo, E.: Resource-bounded measure and randomness. In: Sorbi, A. (ed.) Complexity, Logic and Recursion Theory, Lecture Notes in Pure and Applied Mathematics, pp 1–47. Marcel Dekker, New York, N.Y. (1997)

Ambos-Spies, K., Terwijn, S.A., Zheng, X.: Resource bounded randomness and weakly complete problems. Theoretical Computer Science 172(1–2), 195–207 (1997)MathSciNetCrossRef

Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP has subexponential simulations unless EXPTIME has publishable proofs. Comput. Complex. 3, 307–318 (1993)MathSciNetCrossRef

10.

Balcázar, J.L., Díaz, J., Gabarró, J.: Structural Complexity I, 2nd edn. Springer-Verlag, Berlin (1995)CrossRef

11.

Berman, L.: On the structure of complete sets: Almost everywhere complexity and infinitely often speedup. In: Proceedings of the Seventeenth Annual Conference on Foundations of Computer Science, pp 76–80 (1976)

12.

Berman, L., Hartmanis, J.: On isomorphism and density of NP and other complete sets. SIAM Journal on Computing 6(2), 305–322 (1977)MathSciNetCrossRef

13.

Buhrman, H., Hescott, B., Homer, S., Torenvliet, L.: Non-uniform reductions. Theory Comput. Syst. 47(2), 317–341 (2010)MathSciNetCrossRef

14.

Buhrman, H., van Melkebeek, D.: Hard sets are hard to find. J. Comput. Syst. Sci. 59(2), 327–345 (1999)MathSciNetCrossRef

15.

Hirahara, S.: Identifying an honest EXP^NP oracle among many. In: Proceedings of the 30th Conference on Computational Complexity (CCC 2015), pp 244–263 (2015)

16.

Hitchcock, J.M., Pavan, A.: Comparing reductions to NP-complete sets. Inf. Comput. 205(5), 694–706 (2007)MathSciNetCrossRef

17.

Hitchcock, J.M., Pavan, A.: Hardness hypotheses, derandomization, and circuit complexity. Comput. Complex. 17(1), 119–146 (2008)MathSciNetCrossRef

18.

Hitchcock, J.M., Shafei, H.: Autoreducibility of NP-complete sets under strong hypotheses. Comput. Complex. 27(1), 63–97 (2018)MathSciNetCrossRef

19.

Juedes, D.W., Lutz, J.H.: Weak completeness in E and E₂. Theor. Comput. Sci. 143(1), 149–158 (1995)CrossRef

20.

Kabanets, V., Cai, J.Y.: Circuit minimization problem. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pp 73–79 (2000)

21.

Karp, R.M., Lipton, R.J.: Turing machines that take advice. Enseign. Math. 28, 191–201 (1982)MathSciNetMATH

22.

Klivans, A., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput. 31(5), 1501–1526 (2002)MathSciNetCrossRef

23.

Lutz, J.H.: Almost everywhere high nonuniform complexity. J. Comput. Syst. Sci. 44(2), 220–258 (1992)MathSciNetCrossRef

24.

Lutz, J.H.: The quantitative structure of exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp 225–254. Springer-Verlag (1997)

25.

Lutz, J.H., Karp-Levin, E. Mayordomo. Cook versus: Separating completeness notions if NP is not small. Theor. Comput. Sci. 164(1–2), 141–163 (1996)CrossRef

26.

Papadimitriou, C.H.: Comput. CompleȦddison-Wesley (1994)

27.

Pavan, A.: Comparison of reductions and completeness notions. SIGACT News 34(2), 27–41 (2003)CrossRef

28.

Pavan, A., Selman, A.L.: Bi-immunity separates strong NP-completeness notions. Inform. Comput. 188(1), 116–126 (2004)MathSciNetCrossRef

29.

Valiant, L., Vazirani, V.: NP is as easy as detecting unique solutions. Theor. Comput. Sci. 47(3), 85–93 (1986)MathSciNetCrossRef

Titel: Nonuniform Reductions and NP-Completeness
verfasst von: John M. Hitchcock
Hadi Shafei
Publikationsdatum: 01.06.2022
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 4/2022
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-022-10083-y

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 4/2022

Graph Square Roots of Small Distance from Degree One Graphs

Non-Existence of Stable Social Groups in Information-Driven Networks

The Complexity of Unavoidable Word Patterns

Mechanism Design for Perturbation Stable Combinatorial Auctions

Second-Order Finite Automata

On Random Perfect Matchings in Metric Spaces with Not-too-large Diameters

Premium Partner