Sottoinsieme con condizione modificata, è ancora complesso NP? [Chiuso

Question

Quindi so che le condizioni richieste per un problema per essere NP-complete è che deve trovarsi all'interno di NP e deve essere H-Hard.

Il problema dato che ho è la somma del sottoinsieme.

Tuttavia, le condizioni sono state cambiate in somma ≤ m e somma ≥ m dalla somma = M. per essere più specifici:

1. "Se chiediamo se esiste un sottoinsieme con somma ≤ m, il problema è ancora completo?"

2. "Se chiediamo se esiste un sottoinsieme con somma ≥ m, il problema è ancora completo?"

La mia reazione iniziale è che i due problemi non sono più completi NP poiché possono essere entrambi risolti nel tempo polinomiale.

1. Controlla ogni elemento e vedi se esiste almeno uno più piccolo di M.
2. Aggiungi tutti i numeri interi positivi e vedi se la somma di tutti gli elementi è più grande di M.

Dal momento che non è difficile, non può quindi essere NP-completo.

Sto pensando/avvicinando a questo correttamente?