average-case hard problem
C50275
concept
An average-case hard problem is a computational problem for which solving randomly chosen instances (under some natural input distribution) is believed to be infeasible for any efficient algorithm, not just the worst-case instances.
Instances (1)
| Instance | Via concept surface |
|---|---|
|
short integer solution (SIS) problem
surface form:
short integer solution problem
|
— |