Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 2/2012

01.08.2012

Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses

verfasst von: Xiaoyang Gu, John M. Hitchcock, A. Pavan

Erschienen in: Theory of Computing Systems | Ausgabe 2/2012

Einloggen

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

search-config
loading …

Abstract

This paper presents the following results on sets that are complete for NP.
(i)
If there is a problem in NP that requires \(2^{n^{\Omega(1)}}\) time at almost all lengths, then every many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits.
 
(ii)
If there is a problem in co-NP that cannot be solved by polynomial-size nondeterministic circuits, then every many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits.
 
(iii)
If there exist a one-way permutation that is secure against subexponential-size circuits and there is a hard tally language in NP∩co-NP, then there is a Turing complete language for NP that is not many-one complete.
 
Our first two results use worst-case hardness hypotheses whereas earlier work that showed similar results relied on average-case or almost-everywhere hardness assumptions. The use of average-case and worst-case hypotheses in the last result is unique as previous results obtaining the same consequence relied on almost-everywhere hardness results.
Vorheriger Artikel Inseparability and Strong Hypotheses for Disjoint NP Pairs

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
Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009) MATH
2.
Amir, A., Beigel, R., Gasarch, W.: Some connections between bounded query classes and non-uniform complexity. Inf. Comput. 186, 104–139 (2003) MATHCrossRefMathSciNet
3.
Agrawal, M.: Pseudo-random generators and structure of complete degrees. In: Proceedings of the Seventeenth Annual IEEE Conference on Computational Complexity, pp. 139–147 (2002)
4.
Ambos-Spies, K., Bentzien, L.: Separating NP-completeness notions under strong hypotheses. J. Comput. Syst. Sci. 61(3), 335–361 (2000) MATHCrossRefMathSciNet
5.
Agrawal, M., Watanabe, O.: One-way functions and the isomorphism conjecture. Technical report TR09-019, Electronic Colloquium on Computational Complexity, 2009
6.
Beigel, R.: Query-limited reducibilities. PhD thesis, Stanford University, 1987
7.
Berman, L.: Polynomial reducibilities and complete sets. PhD thesis, Cornell University, 1977
8.
9.
Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP has subexponential time simulations unless EXPTIME has publishable proofs. Comput. Complex. 3, 307–318 (1993) MATHCrossRefMathSciNet
10.
Buhrman, H., Fortnow, L., Torenvliet, L.: Six hypotheses in search of a theorem. In: IEEE Conference on Computational Complexity, pp. 2–12 (1997)
11.
12.
Buhrman, H., Hitchcock, J.M.: NP-hard sets are exponentially dense unless NP⊆coNP/poly. In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, pp. 1–7. IEEE Comput. Soc., Los Alamitos (2008) CrossRef
13.
14.
Buhrman, H., Homer, S., Torenvliet, L.: Completeness for nondeterministic complexity classes. Math. Syst. Theory 24, 179–200 (1991) MATHCrossRefMathSciNet
15.
Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the Third ACM Symposium on the Theory of Computing, pp. 151–158 (1971)
16.
Feigenbaum, J., Fortnow, L., Laplante, S., Naik, A.: On coherence, random-self-reducibility, and self-correction. Comput. Complex. 7, 174–191 (1998) MATHCrossRefMathSciNet
17.
Feigenbaum, J., Fortnow, L., Lund, C., Spielman, D.: The power of adaptiveness and additional queries in random-self-reductions. Comput. Complex. 4, 158–174 (1994) MATHCrossRefMathSciNet
18.
Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 133–142 (2008)
19.
20.
Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: Proceedings of the Twenty-First ACM Symposium on the Theory of Computing, pp. 25–32 (1989)
21.
Goldreich, O., Levin, L., Nisan, N.: On constructing 1-1 one-way function. Technical report TR95-029, ECCC, 1995
22.
Hemaspaandra, E., Naik, A., Ogiwara, M., Selman, A.: P-selective sets and reducing search to decision vs. self-reducibility. J. Comput. Syst. Sci. 53(2), 194–209 (1996) MATHCrossRef
23.
24.
Hitchcock, J.M., Pavan, A., Vinodchandran, N.V.: Partial Bi-immunity, scaled dimension, and NP-completeness. Theory Comput. Syst. 42(2), 131–142 (2008) MATHCrossRefMathSciNet
25.
Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: Proceedings of the 36th Annual Conference on Foundations of Computer Science, pp. 538–545 (1995)
26.
Impagliazzo, R., Wigderson, A.: P=BPP if E requires exponential circuits: derandomizing the XOR lemma. In: Proceedings of the 29th Symposium on Theory of Computing, pp. 220–229 (1997)
27.
Johnson, S.: A new upper bound for error correcting codes. IRE Trans. Inf. Theory 8(3), 203–207 (1962) MATHCrossRef
28.
Levin, L.: Universal sorting problems. Probl. Inf. Transm. 9, 265–266 (1973). English translation of original in Problemy Peredaci Informacii
29.
30.
Lutz, J.H., Mayordomo, E.: Measure, stochasticity, and the density of hard languages. SIAM J. Comput. 23(4), 762–779 (1994) MATHCrossRefMathSciNet
31.
Lutz, J.H., Mayordomo, E.: Cook versus Karp-Levin: separating completeness notions if NP is not small. Theor. Comput. Sci. 164(1–2), 141–163 (1996) MATHCrossRefMathSciNet
32.
33.
Pavan, A.: Comparison of reductions and completeness notions. SIGACT News 34(2), 27–41 (2003) CrossRef
34.
35.
36.
Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. J. Comput. Syst. Sci. 62(2), 236–266 (2001) MATHCrossRefMathSciNet
37.
Watanabe, O.: A comparison of polynomial time completeness notions. Theor. Comput. Sci. 54, 249–265 (1987) MATHCrossRef
38.
Yao, A.: Theory and applications of trapdoor functions. In: Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pp. 80–91 (1982)
Metadaten
Titel
Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses
verfasst von
Xiaoyang Gu
John M. Hitchcock
A. Pavan
Publikationsdatum
01.08.2012
Verlag
Springer-Verlag
Erschienen in
Theory of Computing Systems / Ausgabe 2/2012
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-011-9365-0

Weitere Artikel der Ausgabe 2/2012

Theory of Computing Systems 2/2012 Zur Ausgabe

OriginalPaper

Representing Hyper-arithmetical Sets by Equations over Sets of Integers

OriginalPaper

The Complexity of the List Homomorphism Problem for Graphs

OriginalPaper

On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography

OriginalPaper

Dispersion in Disks

EditorialNotes

Theoretical Aspects of Computer Science

OriginalPaper

Inseparability and Strong Hypotheses for Disjoint NP Pairs

Premium Partner

    Bildnachweise