UEHARA R(2023)Computational Complexity of Puzzles and Related TopicsInterdisciplinary Information Sciences10.4036/iis.2022.R.0629:2(119-140)Online publication date: 2023
https://doi.org/10.4036/iis.2022.R.06
Shivappa N(2023)A Survey on Classic Examples of Constraint Satisfaction Problems with Solutions and Applications2023 3rd International Conference on Smart Generation Computing, Communication and Networking (SMART GENCON)10.1109/SMARTGENCON60755.2023.10442726(1-7)Online publication date: 29-Dec-2023
https://doi.org/10.1109/SMARTGENCON60755.2023.10442726
Isuzugawa RMiyahara DMizuki T(2021)Zero-Knowledge Proof Protocol for Cryptarithmetic Using Dihedral CardsUnconventional Computation and Natural Computation10.1007/978-3-030-87993-8_4(51-67)Online publication date: 11-Oct-2021
https://doi.org/10.1007/978-3-030-87993-8_4
Show More Cited By

Index Terms

On the NP-completeness of cryptarithms

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

ACM SIGACT News Volume 18, Issue 3

April 1987

36 pages

ISSN:0163-5700

DOI:10.1145/24658

Editor:
Victor S Miller

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1987

Published in SIGACT Volume 18, Issue 3

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
446
Total Downloads

Downloads (Last 12 months)106
Downloads (Last 6 weeks)14

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

UEHARA R(2023)Computational Complexity of Puzzles and Related TopicsInterdisciplinary Information Sciences10.4036/iis.2022.R.0629:2(119-140)Online publication date: 2023
https://doi.org/10.4036/iis.2022.R.06
Shivappa N(2023)A Survey on Classic Examples of Constraint Satisfaction Problems with Solutions and Applications2023 3rd International Conference on Smart Generation Computing, Communication and Networking (SMART GENCON)10.1109/SMARTGENCON60755.2023.10442726(1-7)Online publication date: 29-Dec-2023
https://doi.org/10.1109/SMARTGENCON60755.2023.10442726
Isuzugawa RMiyahara DMizuki T(2021)Zero-Knowledge Proof Protocol for Cryptarithmetic Using Dihedral CardsUnconventional Computation and Natural Computation10.1007/978-3-030-87993-8_4(51-67)Online publication date: 11-Oct-2021
https://doi.org/10.1007/978-3-030-87993-8_4
Nozaki YHendrian DYoshinaka RShinohara A(2018)Enumeration of Cryptarithms Using Deterministic Finite AutomataImplementation and Application of Automata10.1007/978-3-319-94812-6_24(286-298)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1007/978-3-319-94812-6_24
Gustavo GPablo RCarlos CRodrigo LJohn Willmer E(2016)Un algoritmo para el Strip Packing Problem obtenido mediante la extracción de habilidades de expertos usando minería de datosIngeniería, Investigación y Tecnología10.1016/j.riit.2016.06.00317:2(179-190)Online publication date: Apr-2016
https://doi.org/10.1016/j.riit.2016.06.003
(2012)BibliographyHeuristic Search10.1016/B978-0-12-372512-7.00020-1(793-823)Online publication date: 2012
https://doi.org/10.1016/B978-0-12-372512-7.00020-1
Demaine E(2011)BibliographyGames, Puzzles, and Computation10.1201/b10581-21(217-229)Online publication date: 15-Apr-2011
https://doi.org/10.1201/b10581-21
Kilpeläinen P(2011)Using XQuery for problem solvingSoftware: Practice and Experience10.1002/spe.114042:12(1433-1465)Online publication date: 9-Nov-2011
https://doi.org/10.1002/spe.1140
Brown JTrowbridge TSzabo J(2009)The poetic metrics of bpNichol2009 IEEE Toronto International Conference Science and Technology for Humanity (TIC-STH)10.1109/TIC-STH.2009.5444363(933-938)Online publication date: Sep-2009
https://doi.org/10.1109/TIC-STH.2009.5444363
Acuna DParada V(2005)Modeling expert players' behavior through data miningXXV International Conference of the Chilean Computer Science Society (SCCC'05)10.1109/SCCC.2005.1587866(55-64)Online publication date: 2005
https://doi.org/10.1109/SCCC.2005.1587866
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

References

Cited By

Index Terms

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

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations