Let $ G (V, E) $ to be a graph.
Let $ S $ either all of the combinations of $ | V | $ edges.
Let $ A $ And $ B $ to be two subsets of $ S $, or:
- each subset is a collection of all the elements of $ S $ who share a common "global property"
- the overall properties of $ A $ And $ B $ are different
- $ | A | gt 0 $
- $ | B | gt 0 $
- $ | A cap B | geq 0 $
- $ A not subseteq B $
- $ B not subseteq A $
DEFINITION: Aggregate Property, $ P $of $ Q in S $
Given some $ Q in S $, we must examine each element of $ Q $ in order to check the property $ P $.
- Example for $ Q in A $:[sommedesarêtesdans[sumofedgesin[sommedesarêtesdans[sumofedgesin$ Q $] $ leq $ 40
- Example for $ Q $ B $:[bordsdans[edgesin[bordsdans[edgesin$ Q $ Hamiltonian Cycle form in $ G $]
Let $ alpha $ to be an algorithm that returns an element $ A $given $ G $.
Let $ beta $ to be an algorithm that returns an element $ B $given $ G $.
Each point represents an edge of the graph $ G $:
As a reminder, the global properties of A and B are not the same, therefore:
Key idea 1: Any algorithm that starts at level 1 and ends at level 2 and produces a set of edges with a unique relationship, A, must be an algorithm for α and NOT β.
Let $ gamma $ or any algorithm that returns a set of edges having both the properties A and B, and which does not provide one before the other (does not go to level 3, as described below).
By definition, $ gamma $ is an algorithm for $ alpha $.
By definition, $ gamma $ is an algorithm for $ beta $.
So $ alpha $ and $ beta $ can be equal.
Since $ alpha $ and $ beta $ can be equal, A and B are no longer distinct, because they can be insured using the same algorithm, $ gamma $.
So, A and B are actually the same property.
Key idea 2If an algorithm, γ, which starts at level 1 and ends at level 2, produces a set of edges with 2 relations, M and N, then M and N must be identical.
In order to guarantee 2 distinct properties, $ gamma $ must go to a 3rd level:
So now, $ gamma $ has 2 options:
- Carry out $ alpha $then run $ beta $ (worst case = $ | A | $, must search for the output of $ alpha $ who has $ B $-Property)
- Carry out $ beta $then run $ alpha $ (worst case = $ | B | $, must search for the output of $ beta $ who has $ A $-Property)
Given the context above, is the time complexity of any algorithm $ gamma $ (the one that produces a set of edges at the intersection of $ A $ and $ B $, so this product set will have 2 aggregate properties) delimited by the top $ | A | $ or $ | B | $?
If so, and we demonstrate a $ A $ and $ B $ with exponential sizes compared to the input graph, could we use this technique to show that $ gamma $ Should it take an exponential time in the worst case?
This model does not apply to k-SAT because a solution to k-SAT must have only one aggregate property:
- truth values make a true proposition
Whereas a solution for TSP must have 2 aggregate properties:
- sum of edges $ leq L $
- the edges form the Hamiltonian cycle in $ G $