La variabile a deve puntare a un oggetto Elemento, che va creato. La creazione avviene con il costruttore: a = new Elemento().

Una volta creato questo oggetto, va riempito. Il campo numero deve contenere 4, e questo si ottiene con a.numero = 4. Il campo prossimo deve invece contenere l'indirizzo di un altro oggetto.

Questo altro oggetto va creato, per cui serve ancora il costruttore: a.prossimo = new Elemento(). Il nuovo oggetto a.prossimo viene quindi riempito nello stesso modo.

class Elemento {
	int numero;
	Elemento successivo;
}

class Lista {
	public static void main(String[] args) {
		Elemento a;

		a = new Elemento();
		a.numero = 4;
		a.successivo = new Elemento();
		a.successivo.numero = 3;
		a.successivo.successivo = null;
	}
}

Il primo numero di n+1 bit è uno seguito da n zeri, che è 2ⁿ + 0 + … + 0, ossia 2ⁿ. Quindi n bit rappresentano al massimo 2ⁿ-1. Scrivendo le potenze di due è possibile verificare quali numeri sono rappresentabili.

numero potenza massimo
1      2       1
2      4       3
3      8       7
4      16      15
5      32      31
6      64      63
7      128     127

I numeri 30 e 31 sono minori o uguali di 31 (terza colonna), quindi si rappresentano con cinque bit (prima colonna). Invece 32 richiede sei bit.

In alternativa, è possibile convertire i tre numeri in binario e contare quanti bit si ottengono.

Per la rappresentazione in complemento a due dei numeri positivi serve un bit aggiuntivo, quindi 30 e 31 richiedono sei bit mentre 32 ne richiede sette.

Un esempio:

La sua rappresentazione:

({0,1,2,3}, {(0,1), (0,2), (1,2), (1,3), (2,3)})

Le due clique sono {0,1,2} e {1,2,3}.

L'espressione regolare a*b* collima con le sequenze a seguite da sequenze di b, entrambe di lunghezza arbitraria. Una sequenza si può generare con una regola in cui un simbolo non terminale genera il carattere seguito dallo stesso simbolo non terminale. Questo schema va replicato per entrambe le sequenzse.

S → A B
A → a A
A → ε
B → b B
B → ε

Una alternativa è generare la seconda parte dopo la prima. In questo modo, la grammatica è regolare.

A → a A
A → B
B → b B
B → ε

La definizione matematica di NP è l'insieme dei problemi risolti da una macchina di Turing non deterministica in tempo polinomiale. La definizione semplificata come programma e' che sono i problemi che si risovono in Python con un ciclo sui risultati di itertools.combinations() e itertools.permutations() in cui il corpo del ciclo impiega tempo polinomiale.

La definizione di NP-hard è l'insieme dei problemi tali che ogni problema in NP si riconduce a ognuno di essi.

La seconda definizione permette problemi più difficili di NP. Esistono quindi problemi NP-hard che non sono in NP.