All possible combinations for evalution of conditions

Question

Example :

if(A & B)
{
    if(C)
    {
    }

    if(D)
    {
    }
}

We have four different states for all the conditions in this code. 0 represents False and 1 represents true state. * shows that the condition is not valid in this state flow. So in this case, all the possible states are listed below.

A B C D

0 * * *

1 0 * *

1 1 1 0

1 1 0 1

Explanation : In first state (0 * * *), the condition A is true. So there is no role for B in the code. Becuase after evaluating the A itself the if case is failed. Therefore the conditions C and D also are not evaluated. Like wise the three other possible states also.

But is there any already implemented algorithms by which i can find all these states for a particular input. Because this thing turns to be huge complex problem when we try to solve more complex nested code. I think it's very difficult to code an application to give such a result.

If any one knows some kind of already implemented things which may help me, please let me know about the same.

Answer 1

I'm sorry to be the bearer or bad news but this algorithm is impossible for two, very famous reasons.

The Halting Problem

To solve this problem in a Turing-Complete language you would need to solve the The Halting problem. If your example program looked like this:

if(A & B & maybeAnInfiniteLoop())
{
    if(C)
    {
    }

    if(D)
    {
    }
}

Then we would have no theoretic way of know if the function maybeAnInfiniteLoop terminates or not and thus if C and D matter at all or if the only valid states of the booleans are 00*,10*, or 01*, since 11* would never finish and C and D are never reached.

NP-Complete

Now let's suppose your capable of reducing your problem just to boolean expressions. In a subset of your language where you only have IF, AND, OR, NOT and booleans the language is not Turing Complete. It is what is called strongly normalizing. The language of boolean expressions is an example of one such useful language.

However even if we can guarantee that the program halts, an algorithm to decide all meaningful states of booleans in that language is an NP-complete problem. It is, in fact, among the most famous. It's called the Boolean Satisfiability Problem. Notice that in your example you say that C and D are meaningless when either A or B are false. This is because you know that only set of values for A and B that satisfy the expression "A&B" is (1,1). You can do this because it's a very simple expression but an algorithm to solve this in the general case might not finish in your lifetime for some very reasonable inputs.

Is there hope?

The question of P=NP does not have a known answer. In fact, it is possibly the most important open math question today. If P=NP then you're in luck but I wouldn't get your hopes up. The smart money is on P does not equal NP.