Is Hardness Inherent in Computational Problems? Performance of Human and Electronic Computers on Random Instances of the 0-1 Knapsack Problem.
Nitin YadavCarsten MurawskiSebastian SardiñaPeter BossaertsPublished in: ECAI (2020)
Keyphrases
- knapsack problem
- computational problems
- random instances
- constraint satisfaction problems
- exact algorithms
- phase transition
- np hard
- combinatorial problems
- optimal solution
- combinatorial optimization problems
- constraint satisfaction
- dynamic programming
- randomly generated
- lower bound
- optimization problems
- np complete
- hard problems
- constraint programming
- search space
- sat instances
- np complete problems
- greedy algorithm
- reasoning tasks
- worst case
- graph coloring
- satisfiability problem
- scheduling problem
- evolutionary algorithm
- cost function
- search problems
- special case
- approximation algorithms
- branch and bound algorithm