Distributed six-cycle detection
Each computer knows only its own place in a network and can send short messages to neighbors. How many communication rounds are needed to discover whether the network contains a cycle through six different computers?
Algorithms and data structures
Within Algorithms and data structures · Search all subjects
Solving chess
If both sides played perfectly from the ordinary starting position, would chess end in a draw or a forced win? An unbeatable-looking engine does not yet supply that proof.
Integer multiplication complexity
Long multiplication can be improved to O(n log n) bit operations. Is that logarithmic overhead unavoidable, or could multiplying arbitrary n-bit integers get closer to linear time?
Online bin packing competitive ratio
Items arrive one at a time and must be placed immediately into unit-capacity bins. What is the smallest guaranteed long-run overhead compared with packing the whole list after seeing it?