Average Polynomial Time Complexity of Some NP-Complete Problems.

Phan Dinh Dieu Le Cong Thanh Lê Tuân Hoa

Published in: Theor. Comput. Sci. (1986)

Keyphrases

np complete
np complete problems
polynomial time complexity
np hard
satisfiability problem
computational complexity
constraint satisfaction problems
phase transition
randomly generated
sat problem
min cut max flow
search algorithm
state space
decision problems
graph coloring