Theory and Algorithms  Alla ricerca di quello che può essere calcolato e di come calcolarlo.

Planarity Game

Tutto cio' che serve e' un grafo planare.

Immagina un insieme di punti collegati da segmenti. Riesci a spostare i punti in modo tale da non avere segmenti che intersecano tra loro? In genere, le persone sono in grado di risolvere questo tipo di problema velocemente. In gergo si dice che il problema è 'lineare', al raddoppiare dei punti e dei segmenti, il tempo necessario per risolvere il gioco raddoppia.

Immagina lo stesso gioco con linee curve al posto dei segmenti, ed ogni curva interseca al massimo un'altra curva. Pensi sia più facile... eh?!? Questo problema è 'NP-completo', al raddoppiare dei punti e delle linee, il tempo necessario per risolvere il gioco cresce in modo esponenziale. Per risolvere un gioco con trenta punti sono necessari più di cento anni con gli algoritmi conosciuti al giorno d'oggi!

Responsible: Maksym Zavershynskyi

Gold sponsors:
Silver sponsor:
Con la collaborazione di: