There has been quite some research on finding, in layman's terms, where the difficult instances of an NP-complete problem are.
What it comes down to is that there are phase transitions in computational systems that depend on how constrained the problem is.
Consider a sudoku puzzle. If the board is almost empty of numbers then it's easy to solve. If the board is almost full of numbers it's easy to solve. But there's some critical amount of numbers filled in (say half of them) that makes the sudoko most difficult to solve. That's where the phase transition is.
The notion of a phase transition comes from thermodynamics where ice becomes water becomes gas.
Comments
There has been quite some research on finding, in layman's terms, where the difficult instances of an NP-complete problem are.
What it comes down to is that there are phase transitions in computational systems that depend on how constrained the problem is.
Consider a sudoku puzzle. If the board is almost empty of numbers then it's easy to solve. If the board is almost full of numbers it's easy to solve. But there's some critical amount of numbers filled in (say half of them) that makes the sudoko most difficult to solve. That's where the phase transition is.
The notion of a phase transition comes from thermodynamics where ice becomes water becomes gas.
Here's an early paper on phase transition is AI.
https://www.sciencedirect.com/science/article/pii/0004370287...
Here's a later one on phase transitions for the satisfiability problem (SAT).
https://homepages.inf.ed.ac.uk/rbf/MY_DAI_OLD_FTP/rp679.pdf