Article

Cryptocomplexity and NP-Completeness

Authors:

Shimon Even,

Yacov YacobiAuthors Info & Claims

Proceedings of the 7th Colloquium on Automata, Languages and Programming

Pages 195 - 207

Published: 14 July 1980 Publication History

Abstract

No abstract available.

Cited By

View all

Pass RVenkitasubramaniam M(2021)Guest ColumnACM SIGACT News10.1145/3457588.345759852:1(47-69)Online publication date: 16-Mar-2021
https://dl.acm.org/doi/10.1145/3457588.3457598
Glaßer CReitwießner CSelivanov V(2008)The Shrinking Property for NP and coNPProceedings of the 4th conference on Computability in Europe: Logic and Theory of Algorithms10.1007/978-3-540-69407-6_25(210-220)Online publication date: 15-Jun-2008
https://dl.acm.org/doi/10.1007/978-3-540-69407-6_25
Goldreich O(2006)On promise problemsTheoretical Computer Science10.5555/2168303.2168315(254-290)Online publication date: 1-Jan-2006
https://dl.acm.org/doi/10.5555/2168303.2168315
Show More Cited By

Cryptocomplexity and NP-Completeness

Recommendations

Partial Bi-immunity, Scaled Dimension, and NP-Completeness

The Turing and many-one completeness notions for NP have been previously separated under measure, genericity, and bi-immunity hypotheses on NP. The proofs of all these results rely on the existence of a language in NP with almost everywhere hardness.

In ...
P, NP, and NP-Completeness: The Basics of Computational Complexity
Separating NP-Completeness Notions Under Strong Hypotheses
CCC '97: Proceedings of the 12th Annual IEEE Conference on Computational Complexity

J.H. Lutz (1993) proposed the study of the structure of the class NP=NTIME(poly) under the hypothesis that NP does not have p-measure 0 (with respect to Lutz's resource bounded measure. J.H. Lutz and E. Mayordomo (1996) showed that, under this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Proceedings of the 7th Colloquium on Automata, Languages and Programming

July 1980

670 pages

ISBN:3540100032

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 14 July 1980

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Pass RVenkitasubramaniam M(2021)Guest ColumnACM SIGACT News10.1145/3457588.345759852:1(47-69)Online publication date: 16-Mar-2021
https://dl.acm.org/doi/10.1145/3457588.3457598
Glaßer CReitwießner CSelivanov V(2008)The Shrinking Property for NP and coNPProceedings of the 4th conference on Computability in Europe: Logic and Theory of Algorithms10.1007/978-3-540-69407-6_25(210-220)Online publication date: 15-Jun-2008
https://dl.acm.org/doi/10.1007/978-3-540-69407-6_25
Goldreich O(2006)On promise problemsTheoretical Computer Science10.5555/2168303.2168315(254-290)Online publication date: 1-Jan-2006
https://dl.acm.org/doi/10.5555/2168303.2168315
Bogdanov ATrevisan L(2006)Average-case complexityFoundations and Trends® in Theoretical Computer Science10.1561/04000000042:1(1-106)Online publication date: 1-Oct-2006
https://dl.acm.org/doi/10.1561/0400000004
Esponda FAckley EHelman PJia HForrest S(2006)Protecting data privacy through hard-to-reverse negative databasesProceedings of the 9th international conference on Information Security10.1007/11836810_6(72-84)Online publication date: 30-Aug-2006
https://dl.acm.org/doi/10.1007/11836810_6
Yamakami T(2003)Nearly bounded error probabilistic setsProceedings of the 5th Italian conference on Algorithms and complexity10.5555/1757536.1757565(213-226)Online publication date: 28-May-2003
https://dl.acm.org/doi/10.5555/1757536.1757565
Vardy ALeighton FShor P(1997)Algorithmic complexity in coding theory and the minimum distance problemProceedings of the twenty-ninth annual ACM symposium on Theory of computing10.1145/258533.258559(92-109)Online publication date: 4-May-1997
https://dl.acm.org/doi/10.1145/258533.258559
Valiant LVazirani VSedgewick R(1985)NP is as easy as detecting unique solutionsProceedings of the seventeenth annual ACM symposium on Theory of computing10.1145/22145.22196(458-463)Online publication date: 1-Dec-1985
https://dl.acm.org/doi/10.1145/22145.22196

Abstract

Cited By

Recommendations

Partial Bi-immunity, Scaled Dimension, and NP-Completeness

P, NP, and NP-Completeness: The Basics of Computational Complexity

Separating NP-Completeness Notions Under Strong Hypotheses

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations