Over the past several weeks I have started to compile some of the work, namely definitions and some algorithms that can be used to construct a combinatorial space oracle. I have hit a point though where proof techniques will be implemented to demonstrate the witnessing of some expression directly with syntax. This is required and must be rigorous; thus much care to detail must be accounted for; and the outcome is to demonstrate the collapse of PH. Thus, I am in a phase of learning, specifically the details of formally communicating proofs.
In the mean time with the current semester over halfway done, my grades must remain a priority. And homework remains to supersede work.
Friday, March 21, 2008
Saturday, March 1, 2008
Resolving independent negation
The handling of a logical statement, that we would like to see if there exist some validity, is currently done with the method of expressing variables with a boolean assignment and thus there is a maximum of 2^n truth combinations. This is attainable to brute force attack all of the combinations in feasible time bounds for low values of n, however when n increases to even maximal bounds as low as 50 this procedure becomes inefficient; (this is a far approximation, and in actuality, 50 will seem quite high). This would take over 156 computing hours at 2 GHz, feasible. But suppose that we take n = 100, then it would take over 2.0098*10^11 computing centuries at 2 GHz, infeasible. This is where the problem begins to be overwhelming, and why EXPSPACE computation is not practiced commonly, only for small input sizes.
Lets now compare to another mode of computation. Assume that we handle the negation using independent terms, thus for our n variables we can have a maximum of t=2n terms. This is assuming that we use both the original variable and its negation, perhaps the expression will not require the maximal negations, we are then at some value n <= l <= 2n. Now comes to the part of the expression. When the combinatorical space is constructed it takes O(n) synthesis steps to generate a space containing 2^n strings. These represent every truth possibility for the bound of n terms.
But say that we realize that from the expression there are instances of negations of variables in the same conjunction. In the current logic, we would have these destroy themselves. I think now, as direction removes commutativity with the AND operator, we are left with the instance of removal of crucial information about the expression. Thus, for the maximal bounds of the cardinality of terms, should be somewhere in the range from the amount of terms to the amount of terms in the product statement prior to existential operations on the expression. (This maximum may be reduced to somewhere near half of the original amount of instances, but more care will be given to take care of all instances.) This is an approximate neighborhood of how many negation terms will be included in the combinatorical set, and if all were in then satisfiability will always be attained, giving false witnessing; (very bad!).
So even if we are to execute this maximum bound for a combinatorical space construction we would only extend our efficiency by some constant multiplier, and not increase the complexity of the generation: O(kn) -> 2^(kn), but dramatically increase the complexity of the size of our combinatorical space, precisely increasing our base by a multiplier of k.
Lets now compare to another mode of computation. Assume that we handle the negation using independent terms, thus for our n variables we can have a maximum of t=2n terms. This is assuming that we use both the original variable and its negation, perhaps the expression will not require the maximal negations, we are then at some value n <= l <= 2n. Now comes to the part of the expression. When the combinatorical space is constructed it takes O(n) synthesis steps to generate a space containing 2^n strings. These represent every truth possibility for the bound of n terms.
But say that we realize that from the expression there are instances of negations of variables in the same conjunction. In the current logic, we would have these destroy themselves. I think now, as direction removes commutativity with the AND operator, we are left with the instance of removal of crucial information about the expression. Thus, for the maximal bounds of the cardinality of terms, should be somewhere in the range from the amount of terms to the amount of terms in the product statement prior to existential operations on the expression. (This maximum may be reduced to somewhere near half of the original amount of instances, but more care will be given to take care of all instances.) This is an approximate neighborhood of how many negation terms will be included in the combinatorical set, and if all were in then satisfiability will always be attained, giving false witnessing; (very bad!).
So even if we are to execute this maximum bound for a combinatorical space construction we would only extend our efficiency by some constant multiplier, and not increase the complexity of the generation: O(kn) -> 2^(kn), but dramatically increase the complexity of the size of our combinatorical space, precisely increasing our base by a multiplier of k.
Subscribe to:
Posts (Atom)
