Concorso scientifico | F contro Problema NP

Domande:

1. La B contro Un problema NP chiede se tutti i problemi le cui soluzioni possono essere verificate in un dato momento possono anche essere risolti in un periodo di tempo simile. Come viene chiamato questo periodo di tempo ai fini di questo problema?

2. C'è un altro periodo di tempo chiamato ___________ ____. Mentre la risposta alla prima domanda indica una lunghezza che dipende dalla taglia S Dal problema di input sollevato a qualche autorità (es S²), la risposta alla seconda domanda è una lunghezza proporzionale a un numero intero elevato alla dimensione dell'input (ad esempio 2^S). spiritoso S Yazid, 2^S Aumenterà più velocemente di S². colmare le lacune.

3. Nominare l'organizzazione privata con sede in Colorado che offre un premio in denaro di 1 milione di dollari ciascuna per la soluzione di sette problemi irrisolti, uno dei quali è P v. Problema NP.

4. La soluzione del caso P v. Il problema NP ha gravi conseguenze per la crittografia. Ad esempio, l'algoritmo di crittografia delle informazioni ___ sfrutta il fatto che è molto difficile fattorizzare i numeri primi di un numero molto grande entro un dato periodo di tempo. colmare le lacune.

5. X, un matematico americano, nel 1955 scrisse alla National Security Agency statunitense dicendo che credeva che risolvere un problema sufficientemente complesso avrebbe richiesto molto più tempo che verificarne la soluzione. X divenne famoso per il suo lavoro sulla teoria dei giochi. il suo nome.

le risposte:

1. Tempo polinomiale

2. Tempo esponenziale

3. Istituto Clay di Matematica

4. Algoritmo RSA

5. John Nash