[Classi di Complessita] Mi serve un aiuto...

[qwerty86]

Salve a tutti mi sono imbattuto in questo esercizio e non riesco proprio a venirne fuori...potete darmi una mano?

Chiarire se i seguenti linguaggi sono nella classe P e/o nella classe NPC. Giusticare la risposta.

1)QUASI-HAM = {< G >: il grafo G = (E; V ) ha un ciclo semplice che contiene |V|-1 vertici}
2)4-HAM = {< G >: il grafo G = (E; V ) ha un ciclo semplice che contiene 4 vertici}

Pensandoci credo che il primo faccia parte di npc dato che è proprio come il problema del grafo hamiltoniano solo che invece di |V| vertici qui il ciclo può essere di |V|-1 , il secondo penso dia più semplice e possa essere della classe p. Ora...come giustifico le risposte?? Grazie a tutti anticipaamente

[qwerty86]

Nessuno sa darmi una mano?