Article

Free access

Problems, complete in “average” instance

Author:

Leonid A. LevinAuthors Info & Claims

STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computing

Page 465

https://doi.org/10.1145/800057.808713

Published: 01 December 1984 Publication History

PDF eReader

Abstract

Many interesting combinatorial problems were found to be NP-complete. Since there is little hope to solve them fast in the worst case, researchers look for algorithms which are fast just “on average”. This matter is sensitive to the choice of a particular NP-complete problem and a probability distribution of its instances. Some of these tasks were easy and some not. But one needs a way to distinguish the “difficult on average” problems. Such negative results could not only save “positive” efforts but may also be used in areas (like cryptography) where hardness of some problems is a frequent assumption. A concept of “NP-complete random problems” proposed below may serve this purpose.

Cited By

View all

de Dinechin FKumm Mde Dinechin FKumm M(2023)Fixed-Point MultiplicationApplication-Specific Arithmetic10.1007/978-3-031-42808-1_8(203-258)Online publication date: 23-Aug-2023
https://doi.org/10.1007/978-3-031-42808-1_8
Jain APandey O(2014)Non-Malleable Zero Knowledge: Black-Box Constructions and Definitional RelationshipsSecurity and Cryptography for Networks10.1007/978-3-319-10879-7_25(435-454)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10879-7_25
Khamsemanan NSkeith W(2013)Translation-Randomizable Distributions via Random WalksProceedings of the 7th International Conference on Provable Security - Volume 820910.1007/978-3-642-41227-1_15(249-270)Online publication date: 23-Oct-2013
https://dl.acm.org/doi/10.1007/978-3-642-41227-1_15
Show More Cited By

Index Terms

Problems, complete in “average” instance
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
2. Theory of computation
  1. Computational complexity and cryptography
    1. Problems, reductions and completeness

Recommendations

All Natural NP-Complete Problems Have Average-Case Complete Versions

The theory of average case complexity studies the expected complexity of computational tasks under various specific distributions on the instances, rather than their worst case complexity. Thus, this theory deals with distributional problems, defined as ...
On Worst-Case to Average-Case Reductions for NP Problems

We show that if an NP-complete problem has a nonadaptive self-corrector with respect to any samplable distribution, then coNP is contained in NP/poly and the polynomial hierarchy collapses to the third level. Feigenbaum and Fortnow [SIAM J. Comput., 22 (...
On Worst-Case to Average-Case Reductions for NP Problems
FOCS '03: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science

We show that if an NP-complete problem has a non-adaptive self-corrector with respect to a samplable distribution then coNP is contained in AM/poly and the polynomial hierarchy collapses to the third level. Feigenbaum and Fortnow show the same conclusion ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computing

December 1984

547 pages

ISBN:0897911334

DOI:10.1145/800057

Chairman:
Richard DeMillo

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1984

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
363
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)8

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

de Dinechin FKumm Mde Dinechin FKumm M(2023)Fixed-Point MultiplicationApplication-Specific Arithmetic10.1007/978-3-031-42808-1_8(203-258)Online publication date: 23-Aug-2023
https://doi.org/10.1007/978-3-031-42808-1_8
Jain APandey O(2014)Non-Malleable Zero Knowledge: Black-Box Constructions and Definitional RelationshipsSecurity and Cryptography for Networks10.1007/978-3-319-10879-7_25(435-454)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10879-7_25
Khamsemanan NSkeith W(2013)Translation-Randomizable Distributions via Random WalksProceedings of the 7th International Conference on Provable Security - Volume 820910.1007/978-3-642-41227-1_15(249-270)Online publication date: 23-Oct-2013
https://dl.acm.org/doi/10.1007/978-3-642-41227-1_15
Strzalka DGrabowski F(2008)Long-range dependencies in algorithmic computing2008 Conference on Human System Interactions10.1109/HSI.2008.4581502(564-569)Online publication date: May-2008
https://doi.org/10.1109/HSI.2008.4581502
Nickelsen ASchelm B(2005)Average-Case Computations " Comparing AvgP, HP, and Nearly-PProceedings of the 20th Annual IEEE Conference on Computational Complexity10.1109/CCC.2005.4(235-242)Online publication date: 11-Jun-2005
https://dl.acm.org/doi/10.1109/CCC.2005.4
Karg CSchuler R(2005)Structure in average case complexityAlgorithms and Computations10.1007/BFb0015409(62-71)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0015409
Schuler R(2005)Average polynomial time is hard for exponential time under sn-reductionsFoundations of Software Technology and Theoretical Computer Science10.1007/3-540-60692-0_52(240-247)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-60692-0_52
Schuler RYamakami T(2005)Structural average case complexityFoundations of Software Technology and Theoretical Computer Science10.1007/3-540-56287-7_100(128-139)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-56287-7_100
Rolim J(2005)On the formal aspects of approximation algorithmsAdvances in Computing and Information — ICCI '9010.1007/3-540-53504-7_58(24-33)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-53504-7_58
Schelm B(2005)Average-case non-approximability of optimisation problemsProceedings of the 15th international conference on Fundamentals of Computation Theory10.1007/11537311_36(409-421)Online publication date: 17-Aug-2005
https://dl.acm.org/doi/10.1007/11537311_36
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

All Natural NP-Complete Problems Have Average-Case Complete Versions

On Worst-Case to Average-Case Reductions for NP Problems

On Worst-Case to Average-Case Reductions for NP Problems

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations