Events Tagged: "NP-completeness"

2 events with tag "NP-completeness"

1971 ID: 420
Stephen Cook proves SAT is NP-complete, with implications for graph coloring and other problems
ID: 420
1972 ID: 421
Richard Karp shows 21 problems are NP-complete, including many graph problems (clique, coloring, Hamiltonian cycle)
ID: 421