Some lines not broken in BibLaTeX bibliography

Some entries in my bibliography cause Overfull \hboxes for reasons I don't understand. Here are examples:

The above example was fixed by allowing the ISBN to break with \-, but I can't figure out what's wrong with the example below:

This is my main file:

\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage{import}

\usepackage[
backend=biber,
style=alphabetic,
citestyle=alphabetic,
sorting=nyt
]{biblatex}

\begin{document}

\nocite{*}
\printbibliography[title={References}]\label{sec:paperrefs}

\end{document}


And refs.bib:

@inproceedings{Cook1971,
author = {Cook, Stephen A.},
title = {The Complexity of Theorem-Proving Procedures},
year = {1971},
isbn = {9781450374644},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/800157.805047},
doi = {10.1145/800157.805047},
booktitle = {Proceedings of the Third Annual ACM Symposium on Theory of Computing},
pages = {151–158},
numpages = {8},
location = {Shaker Heights, Ohio, USA},
series = {STOC ’71}
}

@InCollection{sep-computational-complexity,
author       =  {Dean, Walter},
title        =  {Computational Complexity Theory},
booktitle    =  {The Stanford Encyclopedia of Philosophy},
editor       =  {Edward N. Zalta},
howpublished =  {\url{https://plato.stanford.edu/archives/spr2017/entries/computational-complexity/}},
year         =  {2017},
edition      =  {Spring 2017},
publisher    =  {Metaphysics Research Lab, Stanford University}
}

@misc{Friedman2002,
author = "E. Friedman",
title  = "Pushing blocks in gravity is NP-hard",
year   = "2020"
}

@article{Garey1976,
title={The Planar Hamiltonian Circuit Problem is NP-Complete},
author={M. R. Garey and David S. Johnson and Robert E. Tarjan},
journal={SIAM J. Comput.},
year={1976},
volume={5},
pages={704-714}
}

@inproceedings{Demaine2001,
title={Pushing blocks is np-complete for noncrossing solution paths},
author={Erik D. Demaine and Michael Hoffmann},
booktitle={CCCG},
year={2001}
}

@phdthesis{Uehara1998,
title    = {Probabilistic Algorithms and Complexity Classes},
school   = {Department of Computer Science and Information Mathematics, The University of Electro-Communications},
author   = {R. Uehara},
year     = {1998}
}

@inproceedings{Uehara1990,
title={Generalized Hi-Q is NP-Complete},
author={Ryuhei Uehara and Shigeki Iwata},
year={1990}
}

@article{Ravikumar2004,
title = "Peg-solitaire, string rewriting systems and finite automata",
journal = "Theoretical Computer Science",
volume = "321",
number = "2",
pages = "383 - 394",
year = "2004",
issn = "0304-3975",
doi = "https://doi.org/10.1016/j.tcs.2004.05.005",
url = "http://www.sciencedirect.com/science/article/pii/S0304397504003688",
author = "B Ravikumar",
keywords = "Peg-solitaire, String rewriting system, Length-preserving, Change-bounded rewriting rule",
abstract = "We consider a class of length-preserving string rewriting systems and show that the set of encodings of pairs of strings 〈s,f〉 such that f can be derived from s using the rewriting rules can be accepted by finite automata. As a consequence, we show the existence of a linear time algorithm for determining the solvability of a given k×n peg-solitaire board, for any fixed k. This result is in contrast to the results of (13) and (1) that the same problem is NP-hard for n×n boards. We look at some related string rewriting systems and find conditions under which the encodings of the pairs 〈s,f〉 where f can be derived from s is regular."
}

@article{Plesnk1979,
title={The NP-Completeness of the Hamiltonian Cycle Problem in Planar Digraphs with Degree Bound Two},
author={J{\'a}n Plesn{\'i}k},
journal={Inf. Process. Lett.},
year={1979},
volume={8},
pages={199-201}
}

@Book{GPC,
AUTHOR        = {Robert A. Hearn and Erik D. Demaine},
TITLE         = {Games, Puzzles, and Computation},
PUBLISHER     = {A K Peters},
MONTH         = {July},
YEAR          = {2009},
length        = {250 pages}
}

@article{Turing1937,
title={Computability and λ-definability},
volume={2},
DOI={10.2307/2268280},
number={4},
journal={Journal of Symbolic Logic},
publisher={Cambridge University Press},
author={Turing, A. M.},
year={1937},
pages={153–163}
}


The Overfull hboxes don't happen if I cite only the Cook1971 entry.

Related questions are usually about URLs, but most URLs in my bibliography seem to break correctly.

Why does this happen, and how can I force my bibliography entries back into text margins?

• As always on the site please post full (but minimal) examples, not sniplets. Then we do not have to guess what the rest of your document looks like. – daleif Feb 19 at 9:47
• Welcome to TeX.SX! Please help us help you and add a minimal working example with bibliography (MWEB) that illustrates your problem. Reproducing the problem and finding out what the issue is will be much easier when we see compilable code, starting with \documentclass{...} and ending with \end{document}. – dexteritas Feb 19 at 9:59
• Probably you have som long words that do not hyphenate. Add a manual hyphenation \- in the word at the point you want it to break. Or add the word to a hyphenation list in you document (\hyphenation{word-to-be-hyph-en-ated next-word-to-be-hyph-en-ated}). The \hyphenation command declares allowed hyphenation points with a - character in the given words. The words are separated by spaces. LaTeX will only hyphenate if the word matches exactly. – Sveinung Feb 19 at 10:23
• @daleif I added a full example. – Hey Feb 19 at 10:32
• Presumably the text you would like to have hyphenated is "NP-Complete". (La)TeX won't hyphenate a word that already contains a hyphen. Counteract this limitation by adding an invisible space: NP-\hspace{0pt}complete. (Why the limitation exists is discussed in Why can words with hyphen char not be hyphenated?.) – barbara beeton Feb 19 at 17:43

The MWE doesn't reproduce the badly broken ISBN for me and the issue in Uehara1990 is much less pronounced. But be that as it may.
Allowing TeX to break the ISBN and NP-Complete massively increases the chance that you get a more nicely broken bibliography, but there is no guarantee that it works in all situations and manual interventions are hard in the bibliography. In How to adjust the breaking in the bibliography? I discuss several methods to improve line breaking in the bibliography.