Rispondendo, presumo che quando dici che "l'oracolo" non può dirti se una singola asserzione è vera o falsa, conosce ancora il suo valore di verità (ad es. valori di verità generati casualmente per asserzioni generiche) .
Lascia che A sia l'insieme delle tue asserzioni. Se A contiene elementi n , la sua cardinalità è: | A | = n . Per prima cosa chiedi all'oracolo quante affermazioni nel set di partenza A sono vere:
-
true ( A ) = true ( a 1 , a < sub> 2 , ..., a n ) = c .
Ora calcoli ogni sottoinsieme di cardinalità n - 1 , quindi quei sottoinsiemi contenenti solo elementi n - 1 ; ogni sottoinsieme può essere definito come segue:
-
A k = { a 1 , a 2 , ..., un k-1 , un k + 1 , ..., un n-1 , un n }.
Il numero di sottoinsiemi che ottieni è n perché di tanto in tanto rimuovi un elemento da n .
Di nuovo, chiedi all'oracolo come possono essere vere le asserzioni in ogni sottoinsieme:
-
true ( A 1 ) = c 1 ;
-
true ( A 2 ) = c 2 ;
- ...
-
true ( A n ) = c n .
E infine, l'ultima operazione è ... Sottrazione. Calcoli la differenza tra c e ogni c k che hai, e scopri quali asserzioni sono vere e quali false.
Esempio: Diciamo che il set A ha 10 elementi e vero ( A ) = 5. Metà delle affermazioni sono vere, l'altra metà false. Ora apriamo la prima affermazione a 1 da A ottenendo il sottoinsieme A 1 , quindi chiedi all'oracolo il valore di true ( A 1 ).
- Se vero ( A 1 ) = 5, significa che nessuna vera asserzione è stata rimossa dall'avvio del set A : a 1 è falso;
- Se vero ( A 1 ) = 4, manca una vera asserzione rispetto a prima: a 1 è vero.
Proseguendo con A 2 , A 3 , ..., A n e sottraendo c a ogni c k ti dirà quali asserzioni sono vere e quali false.
Note: sto assumendo che la funzione true () sia lineare, perché dipende solo dalla dimensione dell'input: se la dimensione dell'argomento è di 50 valori, lì saranno solo 50 operazioni di lettura. È possibile implementare la funzione in modo che il suo argomento sia una struttura dati invece di scrivere ogni singola variabile - ciò è vantaggioso per la scalabilità dell'input.
La matematica che ho usato è molto semplice e la struttura dei dati di cui hai bisogno può essere qualsiasi cosa tu ritenga opportuno.
Inoltre, sei stato costretto a chiedere all'Oracle un gran numero di asserzioni per volta: il set più piccolo con cui ho a che fare contiene n - 1 elementi, che è molto vicino al numero totale di asserzioni di cui tu hai valore voglio capire.