Sottoproblema

Un sottoproblema è una parte di un problema principale. Dato un problema composto da n variabili, un sottoproblema è un sottoinsieme di m variabili ( m<n ). I sottoproblemi sono il prodotto della scomposizione funzionale e possono essere classificati in sottoproblemi indipendenti e sottoproblemi vincolati.

• Sottoproblema indipendente. Un sottoproblema indipendente è un sottoinsieme di variabili prive di legame con le altre variabili del problema. La variabili del sottoproblema sono legate tra loro da vincoli e relazioni. I sottoproblemi indipendenti sono alla base della metodologia di risoluzione top-down dei problemi e della scomposizione funzionale. Quando un problema può essere scomposto in sottoproblemi indipendenti, la soluzione di questi ultimi implica anche la soluzione del problema generale. Date otto variabili ( x₁, ..., x₈ ) del problema e tre sottoproblemi, un esempio di rappresentazione grafica dei sottoproblemi indipendenti è il seguente:
  
• Sottoproblema dipendente ( vincolato ). Un sottoproblema dipendente ( o sottoproblema vincolato ) è un sottoinsieme di variabili del problema, non slegato da vincoli e da relazioni con le altre variabili esterne. Le variabili del sottoproblema vincolato sono legate da vincoli e relazioni sia con le altre variabili del sottoproblema e sia con una o più variabili di altri sottoproblemi. Ad esempio, due sottoproblemi vincolati sono caratterizzati da una o più variabili in comune. Date otto variabili ( x₁, ..., x₈ ) del problema e tre sottoproblemi, un esempio di rappresentazione grafica dei sottoproblemi indipendenti è il seguente:
  
  Quando un problema è scomposto in sottoproblemi dipendenti, la soluzione di questi ultimi non implica anche la soluzione del problema generale. Per giungere alla soluzione del problema generale è necessario che siano soddisfatti anche i vincoli tra i sottoproblemi. Questa tecnica è utilizzata tramite la metodologia del soddisfacimento dei vincoli.

I sottoproblemi consentono di ridurre la complessità di un problema da analizzare. Ad esempio, dato un problema di n variabili, ognuna con dominio pari a d, la complessità del problema è pari a O(dⁿ) e cresce in modo esponenziale con l'aumentare del numero delle variabili (n). Lo stesso problema può essere suddiviso per scomposizione funzionale in sottoinsiemi indipendenti composti da c variabili. In tal modo si ottengono c/n sottoinsiemi, ognuno dei quali ha una complessità pari O(d^c). Essendo dei sottoproblemi indipendenti, la soluzione di tutti i sottoproblemi implica la soluzione del problema generale. Per risolvere tutti i sottoproblemi è necessario un lavoro O(d^c c/n) di complessità inferiore rispetto al precedente. Nel caso dei sottoproblemi indipendenti la complessità aumenta in modo lineare con il numero delle variabili (n) ed è, pertanto, più semplice da risolvere.