P-optimal Threshold Calculation

Preliminaries

Relations are represented as a integer between 0 and 255 inclusive to correspond to all the different truth tables that can represented by 3 variables. Each rows in the truth table is assigned a value (2^n), the complete table is shown below. A relation is then the sum of the rows it includes. For example relation 22 includes 3 rows, 1, 2, and 4 that sum to 22.
({{"", "Var 1", "Var 2", "Var 3", "Value"}, {0, False, False, False, 1}, {1, False, False, True, 2}, {2, False, True, False, 4}, {3, False, True, True, 8}, {4, True, False, False, 16}, {5, True, False, True, 32}, {6, True, True, False, 64}, {7, True, True, True, 128}})

appSAT generation

The includeRow formula is used to determine if a particular row in the truth table for a relation should be included. r is a power of 2 and represents one of the 8 possible rows that a relation's truth table can include.

The satisfyingRows formula is used to calculate the (Subscript[q, s])(R) for a given relation. s is used to select rows from the truth table that contain s ones (or true values).

The appSAT formula calculates the look-ahead polynomial for a relation. In this case the rank or r(R) is fixed at 3 to correspond with the relation encoding system used.

As we are primarily interested in looking at pairs of relations the combineTwo formula produces a look-ahead polynomial of two relations with unknown fractional portions for each relation.

Maximizing x with known percentages

If the values of t1 and t2 are known the Maximize function can be used to solve the look-ahead polynomial over the range 0≤x≤1. Based on the output of combineTwo and the value of t1 the maxX function will calculate the maximum bias and the percentage of satisfied constraints.

As an example using 22 as defined above and another relation 170 (which says the variable must be true) with relation 22 used 3/4ths of the time in the formula, maxX produces a symbolic maximum.

maxX[combineTwo[22, 170], 3/4]

To make that a little easier to read Mathematica can create a numerical approximation of the values.

N[%]

Maximizing x with unknown percentages

In order to solve the more general problem of finding a t1 and t2 that produce the worst maximum the problem needs to be broken down further. The Maximize function can not be used with independent variables. In this case because we have a known value for t1 and by extension t2, the only remaining unknown is x. To instead model the maximum with unknown values for t1 and t2 a manual maximum function is created through using Piecewise.

When the look-ahead polynomial is degree 1 with respect to x, the maximum will occur at either x=0 or x=1. The Piecewise function is used to model the choice. Only a test for x=1 being greater than x=0 is made and if that fails the default value for Piecewise is returned which in this case is coded as 0.

When the look-ahead polynomial is degree 2 with respect to x, the maximum will occur at either x=0, x=1, or the stationary point. The Root function is used to find where the derivative of the polynomial is 0, which finds the stationary point. Similar to maxX1 above, the Piecewise function tests to determine which value of x to return.

When the look-ahead polynomial is degree 3 with respect to x, the maximum will occur at either x=0, x=1, or one of the two stationary points. Similar to maxX2 above the Root function is used to find the stationary points and the Piecewise function tests to determine which value of x to return.

To remove the need to manually examine the look-ahead polynomial to determine its degree with respect to x, a branching function is used to return the correct maxX# version. The trivial case of no x being present in the look-ahead polynomial is also handled here by always returning 0.

Finding the worst best case scenario

At this point all of the pieces are in place to minimize the maximum x based on a look-ahead polynomial returned from combineTwo. This produces a value for t1, t2, and the percentage of satisfied constraints in the formula if the two relations are present in the ratios given.

As an example using 22 and 170 again, we can compute the values of t1 and t2 that will produce the worst best case scenario.

minT[combineTwo[22, 170]]

To make that a little easier to read Mathematica can create a numerical approximation of the values.

N[%]

Detecting and correcting invalid cases

Unfortunately this isn't enough to completely solve the problem. An example of such a case is with relation numbers 1 (all false) and 128 (all true). The minimum should be at t1=t2=1/2. Setting x=0 will satisfy any relation number 1, while setting x=1 will satisfy any relation number 128. Setting x to anything else risks not satisfying any relation. However, minT produces an erroneous result:

minT[combineTwo[1, 128]]

The use of Piecewise to model the maximum value doesn't handle cases where the denominator of a stationary point becomes 0. If we look at xSP1 as defined in maxX3 the first root is calculate to be.

Root[(D[combineTwo[1, 128], x] /. x -> #) &, 1]

Clearly when t1=t2=1/2 this stationary point is undefined. The reason for this is that the degree of the look-ahead polynomial changes at t1=t2=1/2, making the symbolic case invalid.

{Exponent[
combineTwo[1, 
          128], 
x], 
Exponent[
combineTwo[1, 128] /. t1 -> 1/2 /. 
          t2 -> 1/2, 
x]}

Handling this case requires detecting if such a point exists and independently determining its value. A comparison can then be made between the minT value and maxX value at the undefined stationary point to see if it produces a worse best case scenario. First a test is defined to see if the two relations are of the same degree since only in this case do we expect the look-ahead polynomial to be the same across all values for t1 and t2.

If the two relations are of the same degree, a check needs to be made to determine if for any value of t1 and t2 the coefficient of the maximum degree becomes zero, dropping the degree of the look-ahead polynomial.

This will produce either an equation where t1 and/or t2 can become equal to 0 or it will return False indicating that no such situation exists based on the 3 assumptions passed to the Refine function. In the case of 1 and 128 it returns a result while in the case of 22 and 128 no such point exists.

{sameDegree[combineTwo[1, 128]], 
maxCoeff[
        combineTwo[1, 128]], 
sameDegree[
        combineTwo[22, 128]], 
maxCoeff[
        combineTwo[22, 128]]}

In the cases where a formula is returned it needs to be solved so that the value of t1 can be passed to the maxX function to determine the proper maximum at that point. The result of the Solve function is a list of values ({{t1 -> (1/2), t2 -> (1/2)}}), in which we want to extract the value t1 should be set to. This is accomplished through the use of the Part function.

In the case of 1 and 128 we know that t1=1/2 is a critical point while in the case of 1 and 22 the critical point exists elsewhere.

{criticalPoint[
        maxCoeff[combineTwo[1, 128]]], 
criticalPoint[
        maxCoeff[combineTwo[1, 22]]]}

Uniform reporting of results

Now that critical points can be detected and corrected it is possible to solve for any two relations. The output of minT and maxX differ in the information reported. To aid in uniformly presenting the results two formatting functions are introduced. One handles inserting the missing t1 and t2 data into the result of maxX and the other calculates the x at the worst best case scenario returned by minT.

For resultAddT the Insert includes the assignment of t1 and t2 and the FlattenAt removes the list that was used to insert them into the result of maxX.

For resultAddX the Part[r,2,1,2] digs into the result of minT to extract the value assigned to t1. The surrounding Part extracts the value that x takes on at that value of t1 while the Insert adds the value of x to the end of the variable assignments.

These two functions can be used to format the results once a determination has been made about how the result should be calculated based on the invalid cases noted above.

{resultAddT[combineTwo[22, 170],  3/4], 
resultAddX[
        combineTwo[22, 170]]}

To make that a little easier to read Mathematica can create a numerical approximation of the values.

N[%]

Putting it all together

The entire process of determining if any critical points exist, calculating that value, and correctly formatting the result is rolled into a function called minMax. This function makes additional checks for trivial cases such as both relations being satisfied by an assignment of all false (OddQ), all true (≥128), or the two relations being the same. If none of those cases is satisfied the maxCoeff is calculated and if the two relations are not the same degree or the maxCoeff doesn't exist, a standard minimization is performed. In all other cases a minimization is performed and the maxCoeff is tested and the minimum of the two is returned.

The calculation of a P-optimal threshold is then performed by calling minMax with the two relations that exist within the formula. Note that due to the complexity of the Piecewise function being used in the Minimize function, certain relationship pairs can take considerable time to compute. As a rough benchmark the computation of relations 1 and 150 on a 1.8 GHz G5 takes approximately 6.5 minutes.

{minMax[1, 128], 
minMax[1, 
        22], 
minMax[22, 170]}

Testing area

The area below can be used to test your own pairs of relations

minMax[15, 240]