Reducibility among Combinatorial Problems

DOI10.1007/978-1-4684-2001-2_9zbMath1467.68065OpenAlexW2401610261WikidataQ110971675 ScholiaQ110971675MaRDI QIDQ4999425

Richard M. Karp

Publication date: 6 July 2021

Published in: Complexity of Computer Computations (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-1-4684-2001-2_9

zbMATH Keywords

combinatorial problemTuring machinepolynomial timeregular expressionlanguage recognitionwords over a finite alphabet

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Discrete mathematics in relation to computer science (68Rxx) Classical models of computation (Turing machines, etc.) (68Q04)